Revisiting `transform_lc_map`

[weikengchen]

Summary

I may hire someone to do a pass over transform_lc_map to see if we can make it faster.

See the following breakdown.

Start: Groth16::Prover ··Start: Constraint synthesis ··End: Constraint synthesis ....................................................25.365s ··Start: Inlining LCs ··End: Inlining LCs ............................................................59.181s ··Start: R1CS to QAP witness map ··End: R1CS to QAP witness map .................................................28.268s ··Start: Compute C ··End: Compute C ...............................................................48.037s ··Start: Compute A ··End: Compute A ...............................................................3.444s ··Start: Compute B in G1 ··End: Compute B in G1 .........................................................2.373s ··Start: Compute B in G2 ··End: Compute B in G2 .........................................................5.497s ··Start: Finish C ··End: Finish C ................................................................9.339µs End: Groth16::Prover ...........................................................172.293s Proof generation for one proof: 178.148426339

Problem Definition

The time transform_lc_map takes seems to be too high. In addition, we may want to see if it can be made parallel.

Proposal

Get a professional analysis of this code.

---

For Admin Use

• [x] Not duplicate issue
• [x] Appropriate labels applied
• [x] Appropriate contributors tagged
• [x] Contributor assigned/self-assigned

[Pratyush]

What's the constraint system being used here? The reported numbers are indeed really high.

[weikengchen]

Nonnative arithmetics: https://github.com/DZK-Labs/ark-yafa/blob/main/benches/curve25519_scalar_mul.rs#L165

This is about 4M constraints I believe.

[Pratyush]

That's surprising that it's that bad on such a small constraint count.