Paper 2024/1531
FLI: Folding Lookup Instances
Abstract
We introduce two folding schemes for lookup instances: FLI and FLI+SOS. Both use a PIOP to check that a matrix has elementary basis vectors as rows, with FLI+SOS adding a twist based on Lasso’s SOSdecomposability. FLI takes two lookup instances $\{\mathbf{a}_1\}, \{\mathbf{a}_2\}\subseteq\mathbf{t}$, and expresses them as matrix equations $M_i\cdot\mathbf{t}^\mathsf{T}=\mathbf{a}_i^\mathsf{T}$ for $i=1,2$, where each matrix $M_i\in\mathbb{F}^{m\times N}$ has rows which are elementary basis vectors in $\mathbb{F}^N$. Matrices that satisfy this condition are said to be in $R_{\mathsf{elem}}$. Then, a folding scheme for $R_{\mathsf{elem}}$ into a relaxed relation is used, which combines the matrices $M_1, M_2$ as $M_1+\alpha M_2$ for a random $\alpha\in\mathbb{F}$. Finally, the lookup equations are combined as $(M_1+\alpha M_2)\cdot \mathbf{t}^{\mathsf{T}} = (\mathbf{a}_1+\alpha \mathbf{a}_2)^\mathsf{T}$. In FLI, only the property that a matrix is in $R_{\mathsf{elem}}$ is folded, and this makes the FLI folding step the cheapest among existing solutions. The price to pay is in the cost for proving accumulated instances. FLI+SOS builds upon FLI to enable folding of large SOSdecomposable tables. This is achieved through a variation of Lasso's approach to SOSdecomposability, which fits FLI naturally. For comparison, we describe (for the first time to our knowledge) straightforward variations of Protostar and Proofs for Deep Thought that also benefit from SOSdecomposability. We see that for many reasonable parameter choices, and especially those arising from lookupbased zkVMs, FLI+SOS can concretely be the cheapest folding solution.
Note: Added acknowledgements
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2024
 Keywords
 zero knowledgeinteractive proofsSNARKlookup argumentfolding scheme
 Contact author(s)

albert @ nethermind io
ignacio @ nethermind io  History
 20241028: last of 2 revisions
 20240930: received
 See all versions
 Short URL
 https://ia.cr/2024/1531
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1531, author = {Albert Garreta and Ignacio Manzur}, title = {{FLI}: Folding Lookup Instances}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1531}, year = {2024}, url = {https://eprint.iacr.org/2024/1531} }