Welcome to the resource topic for 2024/1531
Title:
FLI: Folding Lookup Instances
Authors: Albert Garreta, Ignacio Manzur
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 SOS-decomposability.
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 SOS-decomposable tables. This is achieved through a variation of Lasso’s approach to SOS-decomposability, 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 SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs, FLI+SOS can concretely be the cheapest folding solution.
ePrint: https://eprint.iacr.org/2024/1531
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 .