# ZKHack Puzzles #1 Let's Hash it Out

https://zkhack.dev/events/puzzle1.html

- private key $sk$
- public key $P = sk\cdot G_2$
- message $m$
- message's blake2s hash $h_m = \text{blake2s}(m)$, $h_m$ is a scalar field element with $256$ bits size.
- according to `WINDOW_SIZE = 1;NUM_WINDOWS = 256`, CRH will generate $256$ Points according to the `rng`. Let's use $Q_0, Q_1, \dots, Q_{255}$ present them.
- hash to curve $H(h_m) = h_m[0] \cdot Q_0 + h_m[1] \cdot Q_1 + \cdots + h_m[255] \cdot Q_{255}$
- signature $S = sk \cdot H(h_m)$
- $e(S, G_2) = e(H(h_m), P)$

There are $256$ messages:
$$\begin{align*} S_0 & = h_{m0}[0] \cdot sk \cdot Q_0 + h_{m0}[1] \cdot sk \cdot Q_1 + h_{m0}[2] \cdot sk \cdot Q_2 + \cdots + h_{m0}[255] \cdot sk \cdot Q_{255} \\ S_1 & = h_{m1}[0] \cdot sk \cdot Q_0 + h_{m1}[1] \cdot sk \cdot Q_1 + h_{m1}[2] \cdot sk \cdot Q_2 + \cdots + h_{m1}[255] \cdot sk \cdot Q_{255} \\ S_2 & = h_{m2}[0] \cdot sk \cdot Q_0 + h_{m2}[1] \cdot sk \cdot Q_1 + h_{m2}[2] \cdot sk \cdot Q_2 + \cdots + h_{m2}[255] \cdot sk \cdot Q_{255} \\ \cdots \\ S_{255} & = h_{m255}[0] \cdot sk \cdot Q_0 + h_{m255}[1] \cdot sk \cdot Q_1 + h_{m255}[2] \cdot sk \cdot Q_2 + \cdots + h_{m255}[255] \cdot sk \cdot Q_{255} \end{align*}$$

$$\begin{bmatrix}
h_m[0][0] & h_m[0][1] & h_m[0][2] & \cdots & h_m[0][255] \\
h_m[1][0] & h_m[1][1] & h_m[1][2] & \cdots & h_m[1][255] \\
h_m[2][0] & h_m[2][1] & h_m[2][2] & \cdots & h_m[2][255] \\
\cdots \\
h_m[255][0] & h_m[255][1] & h_m[255][2] & \cdots & h_m[255][255]
\end{bmatrix} \begin{bmatrix} sk \cdot Q_0 \\ sk \cdot Q_1 \\ sk \cdot Q_2 \\ \cdots \\ sk \cdot Q_{255} \end{bmatrix} = \begin{bmatrix} S_0 \\ S_1 \\ S_2 \\ \cdots \\ S_{255} \end{bmatrix}$$

Let use $A$ represent the $h_m$ Matrix, use $Q$ represent $sk \cdot Q_i$ Vectors:

$$A\cdot Q = S \Longrightarrow Q = A^{-1} \cdot S$$

and if we have a new message $m^\prime$, we can get it's signature by $S^\prime = h_m^\prime \cdot Q$

I think it would be dangerous to

The problem is that when hash to curve, first hash to field then $\text{field}*Q$, will be dangerous.

Even though we know how to do it, there are still difficulties. In Rust, there are almost no libraries that can find the inverse of a matrix whose elements are in a finite field. I tried two linear algebra libraries, but they directly returned f32. In Sage, when multiplying a matrix by a vector, the data types of the matrix and vector are not allowed to be inconsistent:

sage solution.sage
Traceback (most recent call last):
  File "/Users/flyq/workspace/github/flyq/zkhack-bls-pedersen/solution.sage.py", line 798, in <module>
    Q = m1.inverse() * S
        ~~~~~~~~~~~~~^~~
TypeError: can't multiply sequence by non-int of type 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'

So, we need use sage to find out the $A^{-1}$, then use Rust to get the $Q$ vector and calculate the signature by $S^\prime = h_m^\prime \cdot Q$

we first used the sage code [here](https://github.com/flyq/zkhack-bls-pedersen/blob/main/solution.sage) to print the $A$ matrix's inverse(`a_inv`), then we need copy the `a_inv`'s values to [rust code](https://github.com/flyq/zkhack-bls-pedersen/blob/main/src/bin/verify-bls-pedersen.rs) and finish the solution.

Whole code: https://github.com/flyq/zkhack-bls-pedersen