Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment