Solutions of Puzzle 6

Solutions of Puzzle 6

## Two solutions to Puzzle 6:

### Solution 1:

In this puzzle, the author proposed a proving system which has vulnerability similar to that in BCTV14. The full detail of BCTV14 proving system can be found at section 1.3 of [BCTV14 attack](https://eprint.iacr.org/2019/119.pdf).

The adversary can produce a "fake" proof(this can pass the check of verifier) for any input of same length given a valid proof for some public input of length `n`. To be more specific, let $\pi = (\pi_A, \pi_A^{\prime}, \pi_B, \pi_B^{\prime}, \pi_C, \pi_C^{\prime}, \pi_K, \pi_H) $. The **key observation** here is that as long as we can find an ***alpha*** pair ($\eta_A, \eta_A^{\prime})$ such that $\eta_A + \text{PI}(x^{\prime}) = \pi_A + \textrm{PI}(x)$, then we can reuse the other parts of the original valid proof.

The above implies that $$\eta_A = \pi_A + \textrm{PI}(x) - \textrm{PI}(x^{\prime}) = \pi_A + \sum_{i=1}^{n} (x_i - x_i^{\prime}) \textrm{pk}_{A, i}. $$ As the BCTV14 trusted setup transcript contains the **extra** alpha pair $(\textrm{pk}_{A, i}, \textrm{pk}_{A, i}^{\prime})$, we can get $\alpha_A * \eta_A$ by the equation: 
$$ \eta_A^{\prime} = \alpha_A * \eta_A = \pi_A^{\prime} + \sum_{i=1}^{n} (x_i - x_i^{\prime}) \textrm{pk}_{A,i}^{\prime}$$ 

In summary, for any public input $x^{\prime}$ of length $n$, the proof that the adversary fake is $\pi^{\prime} = (\eta_A, \eta_A^{\prime}, \pi_B, \pi_B^{\prime}, \pi_C, \pi_C^{\prime}, \pi_K, \pi_H) $. 

The proving system proposed in this puzzle is a simplified version of BCTV14 in the sense that A is equal to B. It's easy to check that the above attack works. 



### Solution 2:

We noticed that in the verifier program, there are no checks against the commited points whether the $H$ is valid.

especially the pairing that checks $P == H/Z$:

```
let d = E::pairing(
        (pk + proof.pi_input) + (pk + proof.pi_input) + proof.pi_output.mul(-E::Fr::one()).into(),
        E::G2Affine::prime_subgroup_generator(),
    ) == E::pairing(proof.pi_H, setup.rho_Z);
​```
```

We can make use of this. Let's construct $H = 0$, in which case P will also be 0.

In order to make $P = 0$, we just need to make sure the private inputs exactly cancel out the public inputs.

$P = 2 * \rho * (pi_1(\tau) * x + pi_2(\tau) * y + pi_3(\tau) * z) - \rho * (op_1(\tau) * x + op_2(\tau) * y + op_3(\tau) * z)$

If $pi_{3} = [- (pi_1(\tau) * x + pi_2(\tau) * y)]$ on G1, so $pk + pi_{input}$ equals the point at infinity.

In order to make the second part equals zero, we can directly pi_output == pi_output_prime = [0] on G1.