Application of Graph Methods for Efficient Quotient Polynomial Evaluation in Halo2

Published on: 
Jan 29, 2024


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:


Written by

Table of Contents

Want to discuss further?

Ingonyama is commited to developing hardware for a private future using Zero Knowledge Proofs.

Get in touch
Get our RSS feed