## 问题定义

给定公钥,一组消息,一组基于消息的签名,基于Bls12_381曲线,使用pedersen hash 做哈希字符串到EC point映射, 完整数据集[参考](https://github.com/kobigurk/zkhack-bls-pedersen/blob/main/src/data.rs).关键函数如下:

pub fn verify(pk: G2Affine, msg: &[u8], sig: G1Affine) {
    let (_, h) = hash_to_curve(msg);
    assert!(Bls12_381::product_of_pairings(&[
        (
            sig.into(),
            G2Affine::prime_subgroup_generator().neg().into()
        ),
        (h.into(), pk.into()),
    ])
    .is_one());
}

pub fn hash_to_curve(msg: &[u8]) -> (Vec<u8>, G1Affine) {
    let rng_pedersen = &mut ChaCha20Rng::from_seed([
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1,
    ]);
    let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();
    let b2hash = blake2s_simd::blake2s(msg);
    (
        b2hash.as_bytes().to_vec(),
        CRH::<G1Projective, ZkHackPedersenWindow>::evaluate(&parameters, b2hash.as_bytes())
            .unwrap(),
    )
}

如何基于任意给定一个message(比如,你的用户名),伪造一个签名,使得verify()通过

## 背景介绍

**BLS 聚合签名验证**

$S$表示聚合签名
$P_i$表示公钥,$P_i=[sk_i]G$
$H(m_i)$ 表示$m_i$->EC point
$S = S1 + S2 +…+ S1000$,

$e(G, S) = e(P1, H(m1)) * e(P2, H(m2)) *…* e(P1000, H(m1000))$

$e(G, S) = e(G, S1+S2+…+S1000)         = e(G, S1) × e(G, S2) *…* e(G, S1000)         = e(G, pk1×H(m1)) *…* e(G, pk1000×H(m1000))         = e(pk1×G, H(m1)) *…* e(pk1000×G, H(m1000))         = e(P1, H(m1)) × e(P2, H(m2)) *…* e(P1000, H(m1000))$

**Pedersen Hash 实现**

[source code](https://docs.rs/ark-crypto-primitives/0.3.0/src/ark_crypto_primitives/crh/pedersen/mod.rs.html#34-50)

关键点:把256bit 输入m映射到椭圆曲线点

$$
H(m) = \sum_{i=1}^{i=256} G_{i} \hspace{1em} \forall b_{i} \in \{1\}
$$

Pedersen 参数将 WINDOW_SIZE 设置为 1 并将 NUM_WINDOWS 设置为256,对应的base point:
$$
Generators = [[G_{1}], [G_{2}], [G_{3}], ..., [G_{256}]]
$$

所以:
对于输入$m_{1}, m_{2}, ..., m_{256}$, 有:
$$
H_{1} = [b_{1,1}]G_{1} + [b_{1,2}]G_{2} + ... + [b_{1,256}]G_{n}
$$
$$
H_{2} = [b_{2,1}]G_{1} + [b_{2,2}]G_{2} + ... + [b_{2,256}]G_{n}
$$
直到
$$
H_{256} = [b_{256,1}]G_{1} + [b_{256,2}]G_{2} + ... + [b_{256,256}]G_{n}
$$

可以利用$m_i$的线性组合,求解系数,进而组合对应的signature
## 解决方法

假设$AX = M$
其中$A$为256个message的bit 表示矩阵:

$$
A = \begin{bmatrix}
b_{1,1} & b_{2,1} ... & b_{256,1} \\
b_{1,2} & b_{2,2} ... & b_{256,2} \\
... \\
b_{1,256} & b_{2,256} ... & b_{256,256}
\end{bmatrix}
$$

$M$为我们要伪造的message bit表示

$X$为我们要计算的系数向量[$x_1,x_2...x_{256}$]

然后就可以伪造签名 $S_{arb} = [x_{1}]S_{1} + [x_{2}]S_{2} + ... + [x_{256}]S_{256}$

## 参考

https://hackmd.io/@benjaminion/bls12-381#BLS-digital-signatures