logUp* lookup protocol

[jimpo]

This task is to implement the logUp* reduction of knowledge for use in the Spark compiler (Spartan, Section 7).

logUp* is an indexed lookup argument with the notable feature that the lookup-up values do not need to be committed. The verification procedure has parameters:

• F: Field
• eval_claim: F - the evaluation of the lookup-up vector at the eval_point
• eval_point: Vec<F> - n-coordinate evaluation point
• transcript

The reduction outputs

• table_eval_point: Vec<F> - the m-coordinate evaluation point of the table multilinear
• table_eval_claim: F - the claimed evaluation of the table multilinear (T) at table_eval_point
• pushforward_eval_claim: F - the claimed evaluation of the pushforward multilinear (Y) at table_eval_point
• index_eval_point: Vec<F> - the n-coordinate evaluation point of the index multilinear
• index_eval_claim: F - the claimed evaluation of the index multilinear (I) at index_eval_point

The caller must then verify the three eval claims. Verifying the reduced (output) claims is out of scope for this task. The logUp* verify routine should verify the evaluation of the X multilinear, which it has sufficient information to do.

[jimpo]

@HiddenAndBound Interested in taking this? I'm happy to hop on a call to help think it through if you'd like.

[HiddenAndBound]

Definitely! Call sounds good!

[jimpo]

Batched logUp* for Spark

Setup

In Spark, we have 3 sparse matrices A, B, C of dimension 2^m × 2^n. Each matrix is represented by three equal-length vectors over the same hypercube:

• row: indices in [0, 2^m), committed
• col: indices in [0, 2^n), committed
• val: indicator polynomial (≤-indicator), succinctly evaluatable

Assume all three matrices have row/col/val padded to equal length (via the val indicator).

Tables

Two lookup tables of equal size 2^k (pad the smaller with dummy variables):

• Table 0: eq(r_y, ·) (row table, originally size 2^m)
• Table 1: eq(r_x, ·) (col table, originally size 2^n)

Reduction Overview

Step 1: Batch Sumcheck

Run a batch sumcheck over the three matrices to verify claims of the form:

$$\sum_x \text{row}_i^_(x) \cdot \text{col}_i^_(x) \cdot \text{val}_i(x)$$

where row* and col* denote pullbacks of eq-indicator polynomials along the row and col index vectors.

This reduces to evaluation claims on row_i, col_i, val_i at a common point z for each matrix i ∈ {A, B, C}.

Step 2: Group Claims by Table

We now have 6 looker columns with evaluation claims at the same point z:

• Table 0 (row): row_A, row_B, row_C
• Table 1 (col): col_A, col_B, col_C

Step 3: Batch Lookers per Table

For each table, sample challenges and batch the looker columns via multilinear extrapolation into a single looker vector. Extrapolate the evaluation claims accordingly.

Step 4: Batch Pushforwards Across Tables

Run logUp* for each table, yielding one pushforward polynomial per table. The key observation: the pushforward polynomials for different tables can be securely batched together via multilinear extrapolation, reducing to a single batched pushforward commitment.

---

Interface Design

• Input: Multiple evaluation claims on equal-length multilinears, each tagged with a table ID. Tables must be equal size (pad if necessary).
• Commitments: One pushforward per table, batched together into a single commitment via multilinear extrapolation.

[HiddenAndBound]

Is the scope of this follow up issue, the mentioned optimisations and amortisations for the lookup argument or also an interface for the Spark protocol?