Paper 2024/839 Original: eprint.iacr.org/2024/839 ↗
Almost optimal succinct arguments for Boolean circuit on RAM
Abstract
The significance of succinct zero-knowledge proofs has increased considerably in recent times. However, one of the major challenges that hinder the prover's efficiency is when dealing with Boolean circuits. In particular, the conversion of each bit into a finite field element incurs a blow-up of more than 100x in terms of both memory usage and computation time. This work focuses on data-parallel Boolean circuits that contain numerous identical sub-circuits. These circuits are widely used in real-world applications, such as proving a large number of hash-preimages in zkEVM and zkBridge. We develop a method for constructing succinct arguments with $2^{-\lambda}$ soundness error and $O(\omega(1)\frac{N}{\log{N}} \log{\log{N}})$ RAM operations, or $O(\frac{N}{\log{N}}\log\log N)$ finite field additions, along with a negligible number of finite field multiplications. Our approach is based on using the GKR protocol to obtain the succinct argument.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2024-05-31: last updated
- 2024-05-29: published
- Short URL
- https://ia.cr/2024/839
- License
- https://creativecommons.org/licenses/by-nc-nd/4.0/
BibTeX
@misc{cryptoeprint:2024/839,
author = {Tiancheng Xie and Tianyi Liu},
title = {Almost optimal succinct arguments for Boolean circuit on RAM},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/839},
year = {2024},
url = {https://eprint.iacr.org/2024/839}
}