Batch DLog PoK
Opened this issue · 2 comments
If we could implement a batch DLog PoK, it'd massively reduce circuit evaluation cost. While Eagen describes a batch eval, AFAICT, it wouldn't have any benefit since we don't have eval costs. We have in-circuit commitment costs to the bits and divisors. We'd have to merge those somehow.
We can't naively do "Prove knowledge of the discrete log of A + B over H" as A might have a non-H component if B has its negative. While, post-commitment, challenging them for "Prove knowledge of the discrete log of A + cB over H" would work, B is ZK and performing that scalarmul in circuit is quite expensive (though perhaps we can prove the security of a half-width scalarmul which would offer perf benefits?).
... We may able to phrase it as not A + cB yet A + Sum(B for _ in 0 .. c)? That may be what Eagen's commentary on batching was was? Yet that'd grow the divisor from points A + Gi for _ in 0 .. 255 (256 in total) to A + B for _ in 0 .. c + Gi for _ in 0 .. 255. We'd have to figure out a reduction for the middle part, which again, may be available in Eagen's research.
This (+0.5x per additional) would let us reduce from a 1024-wide circuit to a 512-wide circuit, halving verification time, for the first 257m outputs.
This would decrease the proof size by a couple hundred bytes thanks to the single vector commitment which would be used for challenges.