Welcome to the resource topic for 2024/839
Title:
Almost optimal succinct arguments for Boolean circuit on RAM
Authors: Tiancheng Xie, Tianyi Liu
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 \cite{zkevm,xie2022zkbridge}. 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 \cite{GKR} to obtain the succinct argument.
ePrint: https://eprint.iacr.org/2024/839
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .