Binyi Chen

@bychen92

Joined on Jun 26, 2020

  • By Binyi Chen SumCheck [LFKN92] is a classical protocol for a prover to convince the verifier that the evaluations of a multivariate polynomial on the boolean hypercube sum to a specific value, without the verifier to redo the evaluations. It has tons of applications in the industry and is a crucial building block in the recent HyperPlonk SNARK that eliminates the use of large FFTs. HyperPlonk is designed as an efficient SNARK solution for proving complex statements (e.g., circuits with more than $2^{30}$ gates), thus motivating researchers to consider the hardware-acceleration perspective of the SumCheck proving algorithm. Recently, Shlomovits published an excellent post that analyzes the hardware-optimization perspective of SumCheck and encourages more research. In this post, we propose a few new techniques for hardware-accelerating SumCheck. The authors are not hardware experts, but hopefully, the ideas can inspire more experts to improve the hardware-friendliness of SumCheck further. Our Contributions We introduce a hardware-friendly algorithm for SumCheck that requires no repetitive read/write from main memory as indicated by Shlomovits’ post. As a minor caveat, it requires that the total memory size of the hardware chips can fit the instance size. E.g., suppose there are L copies of hardware chips being connected. We need the memory size of each chip to be at least n/L to handle any SNARK statements with n constraints. This is not an issue for GPUs that usually have sufficiently large memory (e.g., 8GB) but might be an issue for other memory-scarce hardware. (One might pile more memory-scarce chips to fit the instance size, but we’re unaware whether this strategy incurs additional overhead.) We resolve the above issue by introducing a hardware-friendly algorithm for a variant of SumCheck. The algorithm has similar proving complexity as above but allows the total memory size of the chips to be much smaller. This algorithm can be more friendly to non-GPU hardware like FPGA/ASICs (that use fast-but-small memory like SRAM). Recap of SumCheck We briefly review the SumCheck protocol and refer to HyperPlonk and Shlomovits’ post for more background.
     Like 2 Bookmark