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

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• 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.