PLOOKUP

Exploring the confusing tunnel of PLOOKUP

Introduction and Context

These schemes allow a prover to commit to a polynomial while keeping it hidden, later revealing specific properties without disclosing the entire polynomial. The "plookup" protocol as detailed in the paper "plookup: A Simplified Polynomial Protocol for Lookup Tables" by Ariel Gabizon and Zachary J. Williamson (2020) plookup: A simplified polynomial protocol for lookup tables, addresses a specific challenge: verifying that the values of a committed polynomial $( f )$ at points in a multiplicative subgroup are contained within a lookup table $( t )$. This is crucial for applications in zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), such as batched range proofs, where we need to ensure all polynomial values fall within a specific range.

Background: Commitment Schemes and Polynomial Commitments

To begin, let's define a commitment scheme. A commitment scheme allows a party to commit to a value while keeping it hidden, with two key properties:

• Hiding property: The commitment reveals no information about the committed value.

• Binding property: Once committed, the value cannot be changed.

Polynomial commitment schemes extend this to polynomials, enabling commitments to functions that can encode complex data or computations. For instance, schemes like KZG (Kate, Zaverucha, Goldberg) KZG polynomial commitments allow for succinct commitments and efficient verification of polynomial evaluations, which are foundational for zk-SNARKs.

Problem Statement and Motivation

The plookup protocol tackles the problem of verifying that for each point in a multiplicative subgroup $( H )$ of size $( n+1 )$, the value $( f(\text{point}) )$ is in the lookup table $( t )$, where $( t )$ has $( d )$ elements. This is essential in scenarios like range checks, where we need to prove all values of $( f )$ lie within a specific set without revealing $( f )$.

Previous methods, such as those by Bootle et al. (2016) Efficient zero-knowledge arguments for arithmetic circuits in the discrete logarithm setting, required commitments to several auxiliary polynomials of degree $( d \cdot \log n )$, which could be inefficient for large $( d )$. Plookup simplifies this, requiring only three commitments to auxiliary polynomials of degree $( n )$, offering efficiency gains when $( d \leq n )$ which is most times the case.

Detailed Protocol Steps

The plookup protocol, as outlined in the attachment, involves the following steps, assuming $( d = n+1 )$ for simplicity (padding $( t )$ with repetitions if $( d < n )$):

1. Sorting and Representation:

   • Concatenate the vector $( f \in \mathbb{F}^n )$ (values of the polynomial at $( n )$ points) and $( t \in \mathbb{F}^{n+1} )$ (table values), then sort to get $( s \in \mathbb{F}^{2n+1} )$.

   • Represent $( s )$ using two polynomials $( h_1, h_2 \in \mathbb{F}_{<n+1}[X] )$:

     • $( h_1(\mathbf{g}^i) = s_i ) for ( i \in [n+1] )$,

     • $( h_2(\mathbf{g}^i) = s_{n+i} ) for ( i \in [n+1] ), where ( H = {\mathbf{g}, \ldots, \mathbf{g}^{n+1}=1} )$ is the subgroup.

2. Prover Sends Polynomials:

   • The prover computes and sends $( h_1 )$ and $( h_2 )$ to the verifier.

3. Verifier Sends Random Challenges:

   • The verifier chooses random $( \beta, \gamma \in \mathbb{F} )$ and sends them to the prover.

4. Prover Computes Aggregation Polynomial:

   • The prover computes $( Z \in \mathbb{F}_{<n+1}[X] )$, defined as:

     • $( Z(\mathbf{g}) = 1 )$,

     • For $( 2 \leq i \leq n ): [ Z(\mathbf{g}^i) = \frac{(1+\beta)^{i-1} \prod_{j \leq i} (\gamma + f_j) \cdot \prod_{1 \leq j < i} (\gamma(1+\beta) + t_j + \beta t_{j+1})}{\prod_{1 \leq j < i} (\gamma(1+\beta) + s_j + \beta s_{j+1}) (\gamma(1+\beta) + s_{n+j} + \beta s_{n+j+1})}, ]$

     • $( Z(\mathbf{g}^{n+1}) = 1 )$.

5. Prover Sends Aggregation Polynomial:

   • The prover sends $( Z )$ to the verifier.

6. Verifier Checks Identities:

   • The verifier checks:

     • $( L_1(\mathbf{x})(Z(\mathbf{x}) - 1) = 0 ) (ensures ( Z(\mathbf{g}) = 1 ))$,

     • $[ (\mathbf{x} - \mathbf{g}^{n+1}) Z(\mathbf{x})(1+\beta) \cdot (\gamma + f(\mathbf{x}))(\gamma(1+\beta) + t(\mathbf{x}) + \beta t(\mathbf{g} \cdot \mathbf{x})) = (\mathbf{x} - \mathbf{g}^{n+1}) Z(\mathbf{g} \cdot \mathbf{x})(\gamma(1+\beta) + h_1(\mathbf{x}) + \beta h_1(\mathbf{g} \cdot \mathbf{x}))(\gamma(1+\beta) + h_2(\mathbf{x}) + \beta h_2(\mathbf{g} \cdot \mathbf{x})), ]$

     • $( L_{n+1}(\mathbf{x})(h_1(\mathbf{x}) - h_2(\mathbf{g} \cdot \mathbf{x})) = 0 )$,

     • $( L_{n+1}(\mathbf{x})(Z(\mathbf{x}) - 1) = 0 ) (ensures ( Z(\mathbf{g}^{n+1}) = 1 ))$.

   • Outputs "acc" if and only if all check pass.

The protocol's correctness ensures that if $( {f(\mathbf{g}^i)}{i \in [n]} \not\subset {t(\mathbf{g}^i)}{i \in [n+1]} )$, the verifier accepts with negligible probability, with complexity $( \mathfrak{d}(\mathscr{P}) = 5n + 4 )$.

Key Components and Underlying Concepts

• Sorting Mechanism: The sorting of $( f )$ and $( t )$ transforms the membership problem into checking consistency in the sorted list, handled via polynomials $( h_1 )$ and $( h_2 )$.
• Aggregation Polynomial ( Z ): This polynomial, part of a grand product argument, compactly verifies multiple conditions, leveraging random challenges $( \beta )$ and $( \gamma )$ for zero-knowledge properties.
• Efficiency: By reducing commitments to three polynomials of degree $( n )$, plookup is more efficient than Bootle et al.'s method, especially for $( d \leq n )$.