The write-up of Puzzle 1 - zkhack-bls-pedersen

Puzzle 1 - Let's hash it out.md

From the source code, we can find the authentication system used by Alice is illustrated as:

• Authentication Algorithm (assume the user's message is $m$)

  $${m_hash} = blake2s(m)$$

  $$m_{g1} = hash_to_curve(m_hash)$$

  $$pk = sk* g2$$

  $$ sig = sk*{m_{g1}}$$

• Verification Algorithm

​ $$e(sig, g2) =?\ e(m_{g1}, pk)$$

What's $hash_to_curve$ function?

As defined in ZkHackPedersenWindow,

impl Window for ZkHackPedersenWindow {
    const WINDOW_SIZE: usize = 1;
    const NUM_WINDOWS: usize = 256;
}

One blake2s hash value (256bits) is seperated as 256 windows. That's to say, one window is with one bit. Through random generator, 256 G1 points are randomly selected. The $m_{g1}$ is the sum of those G1 points if the according bit is 1. Assume $g1_{0}, g1_{1}, g1_{2}, ..., g1_{255}$ are randomly selected G1 points, the $hash_to_curve$ can be represented as follows:

​ $$ hash_to_curve = \sum_{i=0}^{255} m_hash[i]*g1_i$$

Let's hash it out

Due to the addition homomorphic of points on elliptic curve, if more than 256 random hashes and according signatures are leaked, the signature of any hash can be "calculated" using the linear combination of leaked signatures. To find the linear combination coefficients ($c_0, c_1 ... c_{255}$), the following equation is used. Assume the leaked 256 hashes is $h_i \ i\in (0, 255)$ and the target hash is $h_t = blake2s(message)$.

$$ \begin{bmatrix} h_{0_0} & h_{1_0} &\cdots & h_{255_{0}} \ h_{0_1} & h_{1_1} &\cdots & h_{{255}{1}} \ \cdots &\cdots &\cdots&\cdots \ h{0_{255}} & h_{1_{255}} &\cdots & h_{{255}{255}}\ \end{bmatrix} \begin{bmatrix} c{0} \ c_{1} \ \vdots \ c_{255} \end{bmatrix} = \begin{bmatrix} h_{t_0} \ h_{t_1}\ \vdots \ h_{t_{255}} \end{bmatrix} $$

Once the coefficients are obtained, the signature of the specified hash can be got:

• $$h_{g1} = \sum_{i=0}^{255} c_i * m_{g1_i}$$

• $$h_{sig} = \sum_{i=0}^{255} c_i * sig_{i}$$

The $h_{sig}$ is exactly what we need.