Abstract
In this work we present our research on applications of graph methods to parallelize the quotient polynomial in the Halo2 Zero-Knowledge Proof (ZKP) system. The evaluation of the quotient polynomial has a complex data-interdependency which makes it a serious compute and memory bottleneck in Halo2 applications.
We achieve partitioning of quotient polynomial evaluation for large circuits, into groups of connected components such that the groups are weakly connected. The weak connections are data that can be copied to the groups at the time of evaluations, thus parallelizing the problem and solving data-interdependency.
As a concrete Proof of Concept, we demonstrate an efficient partition of quotient polynomial evaluation into two independant bins for the Taiko ZK-EVM super circuit in CPU. In a two GPU setup, the two bins can be run completely independently in parallel, thus reducing latency and memory significantly.
Full Paper:
https://github.com/ingonyama-zk/papers/blob/main/halo2_community_detection_research.pdf
.png)
