Welcome to the resource topic for 2024/108
Title:
Some Improvements for the PIOP for ZeroCheck
Authors: Angus Gruen
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.
ePrint: https://eprint.iacr.org/2024/108
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 .