It appears ProjectiveCurve: Hash which sounds slow. I'd expect only AffineCurve: Hash so one must explicitly batch normalize anytime one wants hashes of points.
There is some complexity here because one should minimize pairings in a pairing equation by collecting points in buckets and running roughly Gaussian elimination. It's doable optimally for BLS signatures provided you give yourself some pre-hashed fixed size message type like a [u8; 32], so you can collect those points before even creating any projective points with hash-to-curve.
In general, you need some excess redundency in some batch_normalization calls if you start with only a bunch of projective points on both sides, but any given proof system could've its batch verifier written to do this optimally I think, but you need to look at the specific equation. In the end, all these worries would land under some TIPP/MIPP prover I think.
Pratyush
commented
2 years ago
It appears
ProjectiveCurve: Hashwhich sounds slow. I'd expect onlyAffineCurve: Hashso one must explicitly batch normalize anytime one wants hashes of points.There is some complexity here because one should minimize pairings in a pairing equation by collecting points in buckets and running roughly Gaussian elimination. It's doable optimally for BLS signatures provided you give yourself some pre-hashed fixed size message type like a
[u8; 32], so you can collect those points before even creating any projective points with hash-to-curve.In general, you need some excess redundency in some
batch_normalizationcalls if you start with only a bunch of projective points on both sides, but any given proof system could've its batch verifier written to do this optimally I think, but you need to look at the specific equation. In the end, all these worries would land under some TIPP/MIPP prover I think.