Paper 2024/108
Some Improvements for the PIOP for ZeroCheck
Abstract
Most multivariate proof systems require, at some point, an algebraic check against the rows of the trace. One popular protocol for this is known as zerocheck which is a sumcheck based protocol which proves a constraint function is zero over the $n$dimensional Boolean hypercube. One of the drawbacks of running zerocheck over a small field, is that it usually involves a large number of evaluations of the constraint polynomial over a cryptographically large extension field $\mathbb{G}$. We describe several improvements to the zerocheck protocol over a small field $\mathbb{F}$ which both reduce the number of constraint evaluations the prover needs to perform and shifts some computation from the extension field back into the base field $\mathbb{F}$. Specifically, for a table of length $2^n$, integer parameter $1\leq k \leq n$ and constraint function $C$ of degree $d$ with evaluation costs $C_{\mathbb{F}}, C_{\mathbb{G}}$ we show the protocol can be performed with prover cost roughly \[ 2^n\left(1 + \frac{C_{\mathbb{G}}}{2^k C_{\mathbb{F}}}\right)(d  1)C_{\mathbb{F}}. \] To check the proof, the verifier needs to perform a single interpolation of degree $2^kd$ and $n$ interpolations of degree $d$. Thus varying $k$ allows for a tradeoff between prover and verifier cost.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 SumcheckInteractive Oracle ProofsSNARKS
 Contact author(s)
 agruen @ polygon technology
 History
 20240126: approved
 20240124: received
 See all versions
 Short URL
 https://ia.cr/2024/108
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/108, author = {Angus Gruen}, title = {Some Improvements for the {PIOP} for {ZeroCheck}}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/108}, year = {2024}, url = {https://eprint.iacr.org/2024/108} }