[Grant Application]: ZK.WORK - GPU-based Taiko Prover Optimization

[web3wangyu]

Project Description

The project aims to optimize the halo2 prover using GPUs. This involves accelerating the computationally intensive tasks within the prover, such as MSM and NTT operations, as well as extensive elliptic curve point calculations, in order to reduce the overall prover execution time.

Category

Zero-Knowledge Proofs (ZKP)

Timeline

1. 30 September, 2023: Completion of initial optimization version for MSM and NTT operations.
2. 31, October, 2023: Completion of initial optimization version for halo2 prover.
3. 30, November, 2023: Completion of high-performance optimization version for halo2 prover, source code will be open-sourced.

Project Plan

We will optimize the prover at various levels:

1. Big integer modular multiplication: Develop a high-performance implementation of big integer modular multiplication for CUDA hardware architecture, based on the Montgomery reduction algorithm.
2. Point addition: Utilize batch inversion for efficient point addition calculations.
3. MSM optimization: Implement an improved version of MSM based on the Pippenger's algorithm.
4. NTT optimization: Rapidly implement NTT optimization using the butterfly algorithm.
5. Remaining components: Achieve high-performance implementation on GPU, optimizing the overall prover workflow.

Project Impact

We will provide an open-source, high-performance CUDA version of the halo2 prover, allowing community developers to further build high-performance halo2 applications on top of this foundation.

Team Information

Lei Hu: Head of Optimization Team

• With 5 years of CUDA optimization experience and 2 years of ZKP program optimization experience
• Master & Bachelor of BUAA

MentWang: Developer

• With 2 years of ZKP program optimization experience
• Master of FDU

ZhiYu: Researcher

• With 2 years of research experience
• Master of NUS & Bachelor of FDU

Point of Contact

https://medium.com/@zk.work

Previous Work

In the aleo prover testnet3 incentivized testing, our team achieved the second-place position with a speed of 3500+ pps/s. Subsequently, we adopted the concepts from ECNTT and continued refining our approach. As a result, the performance of our aleo prove program now surpasses the efficiency of the first-place participant in the previous incentivized testing. Our team has accumulated substantial experience in ZKP optimization and our research efforts in optimization are ongoing. We are poised to achieve even more remarkable results in the field of ZKP optimization in the future.

Additional Information

No response

Agreement

• I agree to comply with the terms and conditions of the grants program