zkhack-double-trouble

zkhack-double-trouble

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

Above is the original display from ZKHack Puzzle 3. In this puzzle, a commitment scheme was described. The scheme is basically a Pedersen Commitment, plus inner product features. If you are not familiar with Pedersen Commitment, here is a [super clean explanation](https://crypto.stackexchange.com/a/64443).



## The Commitment Scheme

Let's go over the scheme used in the puzzle. We divide it into four phases: *PreCommit*, *ProofCommit* , *ProofResponse* and *Verify*.

#### PreCommitment

Prover computes an inner product of the committed vector $$\overrightarrow a$$  and the Common Reference String $$\overrightarrow G$$ , then hiding it with another random group element $$\alpha H$$ . Note that $$\overrightarrow a$$ and $$\alpha$$ are only known by the prover, and $$b$$ is not available yet.
$$
\begin{split}
C_a & = PC(\overrightarrow a; \alpha) \\
&=\langle \overrightarrow a, \overrightarrow G \rangle + \alpha H
    \\ & = \sum_{i=1}^{n} a_ig_i + \alpha H
\end{split}
$$

#### ProofCommitmennt

When prover receives the public vector $$\overrightarrow b$$ , it calculates several commitments: $$C_r, C_1$$  and $$C_2$$ and publish. The inner product $$\langle \overrightarrow a , \overrightarrow b \rangle$$ is also calculated and published, although not used in the puzzle. Those $$\overrightarrow r$$, $$\rho$$, $$\tau$$, $$\upsilon$$ are all randomly sampled.
$$
C_r = \langle \overrightarrow r, \overrightarrow G \rangle  + \rho H \\

C_1 = \langle \langle \overrightarrow a, \overrightarrow b \rangle , \overrightarrow G \rangle  + \tau H \\

C_2 = \langle \langle \overrightarrow r, \overrightarrow b\rangle ,\overrightarrow G\rangle  + \upsilon H
$$

#### ProofResponse

In interactive proofs, verifier sends a challenge $$\gamma$$ and prover needs to calculate $$s$$, $$u$$ and $$t$$ . Here the protocol used **Fiat-Shamir Heuristic** to make the challenge process non-interactive. If you are not familiar with Fiat-Shamir Heuristic, to put it in a nut shell, it replaces the challenge $$\gamma$$ with a uniformly sampled hash function $$H(m)$$ , where $$m$$ is the transcript between prover and verifier so far.

$$
\overrightarrow s = \overrightarrow a + \gamma \overrightarrow r \\
u = \alpha + \gamma \rho \\
t = \tau + \gamma \upsilon
$$

#### Verify

In *Verify* phase, the verifier check two equations:
$$
\begin{split}
PC(\overrightarrow s; u) &= \langle \overrightarrow s,\overrightarrow G \rangle + uH \\
& = \langle \overrightarrow a + \gamma \overrightarrow r, \overrightarrow G\rangle  + (\alpha + \gamma \rho) H \\
& = \langle \overrightarrow a, \overrightarrow G\rangle  + \alpha H + \langle \gamma \overrightarrow r, \overrightarrow G\rangle  + \gamma \rho H \\
& = C_a + \gamma C_r
\end{split}
$$

$$
\begin{split}
PC(\langle \overrightarrow s, \overrightarrow b\rangle ; t) &= \langle \langle \overrightarrow s, \overrightarrow b\rangle , \overrightarrow G\rangle  + tH \\ &= \langle \langle \overrightarrow a + \gamma \overrightarrow r, \overrightarrow b\rangle , \overrightarrow G\rangle  + tH \\
&= \langle \langle \overrightarrow a + \gamma \overrightarrow r, \overrightarrow b\rangle , \overrightarrow G\rangle + (\tau + \gamma \upsilon)H \\
&= \langle \langle \overrightarrow a, \overrightarrow b\rangle , \overrightarrow G\rangle  + \tau H + \langle \langle \gamma \overrightarrow r, \overrightarrow b\rangle , g\rangle  + \gamma \upsilon H \\
&= C_1 + \gamma C_2
\end{split}
$$

## The "Looking Around"

The commitment scheme looks OK. **Completeness** and **Soundness** properties are maintained with no doubt. What about **Zero Knowledge**? There are a lot of random numbers involved in the protocol, $$\overrightarrow a$$ is hided by $$\overrightarrow r$$ and $$\alpha$$ is hided by $$\rho$$ . In order to extract them, we need to solve the discrete logarithm problem, which is not computationally viable.

Let's still take a look at the two public vectors $$\overrightarrow b_1$$ and $$\overrightarrow b_2$$ and see if we can do something. Surprisingly, we found that they were the same! The verifier must be thinking about the same thing!

```shell
instance1.b[0] = Fp256 "(08180E66A534AADEBC88D09E1397DC7C33E2014115EB973B489E7D5CDBF839CD)"
instance1.b[1] = Fp256 "(036AFB822FAC04AC9191CCEEF5BF4E27ADA6DC0440C88ECF3E06DC2FAFB162E6)"
instance1.b[2] = Fp256 "(0DE7FE23DCF79F2A041E2C21876F9B9AEB3F2BC628E07B87F52DF460408334F2)"
instance1.b[3] = Fp256 "(0891BBE1E3DA5717F7ED59288C9F51186E7BBAE018C9DA56F4BC8B4BBBD7457E)"
instance1.b[4] = Fp256 "(05D81F4C416350A3D02B1685176BFE5A98FA15D51C84DBD47680326F9F005E96)"
instance1.b[5] = Fp256 "(06D5E58667508A24F3A3FFBB244575DE29ECB3408D6EBC6D3DCDEFF02AA9453C)"
instance1.b[6] = Fp256 "(06BC47A67C6BD353EE624051B4C4A6A28E7F8CEDB6ED65A007D897AC071CBDCB)"
instance1.b[7] = Fp256 "(0CF6D9D35E0B6F2309568E5BB7C19448D993D2EFFEF7B3D77C137A26C524315A)"
```

```shell
instance2.b[0] = Fp256 "(08180E66A534AADEBC88D09E1397DC7C33E2014115EB973B489E7D5CDBF839CD)"
instance2.b[1] = Fp256 "(036AFB822FAC04AC9191CCEEF5BF4E27ADA6DC0440C88ECF3E06DC2FAFB162E6)"
instance2.b[2] = Fp256 "(0DE7FE23DCF79F2A041E2C21876F9B9AEB3F2BC628E07B87F52DF460408334F2)"
instance2.b[3] = Fp256 "(0891BBE1E3DA5717F7ED59288C9F51186E7BBAE018C9DA56F4BC8B4BBBD7457E)"
instance2.b[4] = Fp256 "(05D81F4C416350A3D02B1685176BFE5A98FA15D51C84DBD47680326F9F005E96)"
instance2.b[5] = Fp256 "(06D5E58667508A24F3A3FFBB244575DE29ECB3408D6EBC6D3DCDEFF02AA9453C)"
instance2.b[6] = Fp256 "(06BC47A67C6BD353EE624051B4C4A6A28E7F8CEDB6ED65A007D897AC071CBDCB)"
instance2.b[7] = Fp256 "(0CF6D9D35E0B6F2309568E5BB7C19448D993D2EFFEF7B3D77C137A26C524315A)"
```

Although $$\overrightarrow b$$ and $$\overrightarrow b'$$ are the same, the commitment $$C_1$$ and $$C_1'$$ are different. That means the random number $$\tau$$ and $$\tau'$$ sampled in two proving process are different. So we can't get much information from here.

```shell
proof1.commitment.comm_1 = GroupAffine { x: Fp256(BigInteger256([5889380100562879757, 1628294439710755145, 2626168617729063945, 7120164517412251841])), y: Fp256(BigInteger256([9406288775899695953, 850357500225795
5456, 11504517710866594476, 4557262803875848464])) }
```

```shell
proof2.commitment.comm_1 = GroupAffine { x: Fp256(BigInteger256([13026460175427331559, 3774823916911062391, 9295953901993867574, 2360200364824642418])), y: Fp256(BigInteger256([368146702619205242, 7092049959963297409, 15822826745894538357, 7191143505535739388])) }
```

Wait a minute, does Bob just say that he get a 2X performance boost on his new proprietary prover? The word "2X" is very suspicious here. How did he achieve that?

## The Prover

As a ZK-focused team, we've done a lot of optimizations on various zero knowledge proving systems, so we are quite sensitive about prover performance. Basically there are two time-consuming processes in recent ZK proving systems: the Polynomial computation and the Multiexp. Polynomial computation takes lots of time when the system tries to constrain witnesses to satisfy linear equations, while Multiexp happens when you want to commit vectors of field elements into some curve points.

In the commitment scheme of this puzzle, there is no polynomial computation, so we know that the most time-consuming operation is Multiexp. To be more specific, the "inner product" of $$\langle \overrightarrow a, \overrightarrow G \rangle$$ and $$\langle \overrightarrow r, \overrightarrow G \rangle$$.

To follow the scheme, Bob must calculate both $$\langle \overrightarrow a, \overrightarrow G \rangle$$ and $$\langle \overrightarrow r, \overrightarrow G \rangle$$. However to improve prover performance, it is possible that Bob only calculate $$\langle \overrightarrow r, \overrightarrow G \rangle$$ once, and save the result for further commitments. In such way, Bob's claim of "2X faster" is real, but **Zero Knowledge** property can be holded no more.

## The Hack

There are sevaral ways that Bob might adopt to "optimize" the prover. The first is to save the result of $$\langle \overrightarrow r, \overrightarrow G \rangle$$ and use it later on to get $$k\langle \overrightarrow r, \overrightarrow G \rangle$$ , while still sampling a new $$\rho'$$. In this case, the new commitment would be like $$C_r' = k\langle \overrightarrow r, \overrightarrow G \rangle + \rho' H$$. Only at a small cost of computation on getting $$k\langle \overrightarrow r, \overrightarrow G \rangle$$ and $$ \rho' H$$.

The second is to save $$C_r = \langle \overrightarrow r, \overrightarrow G \rangle + \rho H$$ and since the commitment scheme is addictively homomorphic, Bob can make some random numbers times the old $$C_r$$ and get newmaintained $$C_r' = kC_r$$. 

There are still too many possibilities. Luckily, by looking into the commitments $$C_r$$ and $$C_r'$$, we found that
$$
C_r' = 2C_r
$$
which means
$$
2\langle \overrightarrow r, \overrightarrow G \rangle + 2 \rho H= \langle \overrightarrow r', \overrightarrow G \rangle + \rho' H \\
2\sum r_ig_i + 2\rho H = \sum r'_ig_i + \rho' H
$$
Since $$\overrightarrow r$$ and $$\rho$$ are randomly sampled (according to Bob!), we know that with a very high probability that
$$
2r_i = r'_i, 2\rho = \rho'
$$
We can use the above equations to compute
$$
u = \alpha + \gamma \rho \\
u' = \alpha + 2\gamma' \rho \\
$$
then $$\alpha$$ can be extracted by
$$
\rho = \frac{u-u'}{\gamma - 2\gamma'} \\
\alpha = u - \gamma \rho = u - \gamma \frac{u-u'}{\gamma - 2\gamma'}
$$
Similarly, we have
$$
s_i = a_i + \gamma r_i \\
s_i' = a_i + 2\gamma r_i'  \\
$$
Thus extract $$\overrightarrow a$$ by
$$
r_i = \frac{s-s'}{\gamma - 2\gamma'} \\
a_i = s_i - \gamma r_i = s_i - \gamma \frac{s_i-s_i'}{\gamma - 2\gamma'}
$$
We can use rust to do all the calculations

```rust
let c1 = challenge(&ck, &instance1, &proof1.commitment);
let c2 = challenge(&ck, &instance2, &proof2.commitment);
let u1 = proof1.response.u;
let u2 = proof2.response.u;
let n_2 = Fr::from_str("2").unwrap();

let rho = (u2 - u1) / (n_2 * c2 - c1);
let alpha = u1 - c1 * rho;
println!("alpha = {}", alpha)

// then we get alpha
// alpha = Fp256 "(039356E0074288047BE3CD30583A88B7A760D6AFC2C1E996C33A41684D989534)"

let mut r_v = Vec::new();
for i in 0..proof1.response.s.len() {
    let s = proof1.response.s[i] - proof2.response.s[i];
    let c = c1 - n_2 * c2;
    r_v.push(s / c);
    // println!("r[{}] = {}", i, s / c);
}

let mut a_v = Vec::new();
for i in 0..proof1.response.s.len() {
    let a = proof1.response.s[i] - (c1 * r_v[i]);
    a_v.push(a);
    println!("a[{}] = {}", i, a);
}

// extract `a`
// a[0] = Fp256 "(052A875D7E3F3F47D964D8D03C9C96BAC72690BD62D529233A5F196EA626DA47)"
// a[1] = Fp256 "(0709F70E0787B6F99008CAD06522A40A7C4A0B4D62E8029B7073F64D6832E97C)"
// a[2] = Fp256 "(0B72FDA7B32B74DF0EE544558104AE1B79318A4BF2F768F045140EA48EE8CC2E)"
// a[3] = Fp256 "(04CFCDCCAF8D3DA832B5F677B3D20B27444C77AB52901ABA1C4F4A124C6C8BFA)"
// a[4] = Fp256 "(0BBDE6DD34E9A0C21118ACAB8083F6308F297DB567D3AC7DF3BE555335FECC85)"
// a[5] = Fp256 "(0CD666318404B4C1042C3B1646E32F072A10C30F05FAA2701A3F25C987470DB5)"
// a[6] = Fp256 "(023961D1A8FCD42B7BB8EEE8CBCBE46A1FAEBB65320BABF09A635FDF8C9821F9)"
// a[7] = Fp256 "(03A52AF29CA3C162D31CD9D8E8937B652E0BCEC0E3C03270E3F82C91920C2A56)"
```