# LogUp\* ## Introduction [LogUp](/intro/zk/lookup/logup-gkr.md#logup) was originally designed as a protocol to prove **non-indexed lookup arguments**. In contrast, permutation arguments are defined in the **indexed lookup form**, and one typically reduces indexed lookup to non-indexed lookup in order to apply LogUp. A non-indexed lookup argument deals with the problem of proving that, for two arrays $$X, T$$ with $$|X| = n, |T| = m$$, the relation $$X \subseteq T$$ holds. In contrast, an indexed lookup argument introduces an **index array** $$I$$ in place of $$X$$ to carry out the proof. (Let's see how $$I$$ looks like later!) LogUp\* focuses on the following setting: 1. $$m \ll n$$ ⇒ small table 2. $$I$$ consists of $$n$$ small elements. 3. $$T$$ consists of $$m$$ large elements ≈ 128-bit In this situation, the standard reduction requires committing to the array $$I^\*T$$ (the [pullback](#pullback-and-pushforward)). While elliptic curve–based commitments offer some solutions, hash-based commitments do not provide an efficient method. The problem becomes particularly severe when the elements of $$I^\*T$$ must be defined over an extension field in order to achieve 128-bit security; the commitment cost grows prohibitively large according to the paper, roughly 6× the cost compared to plain LogUp. LogUp\* addresses this challenge by proposing an efficient alternative that is **agnostic to both the underlying field and the commitment scheme**. *** ## Background ### Non-indexed lookup * Pre-commitment: $$X, T, \mathsf{acc}$$ ($$\mathsf{acc}$$, also called the **multiplicity** , indicates how many times each table element in $$T$$ is looked up by $$X$$). * Claim: $$X \subseteq T$$ * Challenge: $$c$$ * Verification: $$ \sum\_{0 \le i < n}\frac{1}{c - X\[i]} = \sum\_{0 \le j < m} \frac{\mathsf{acc}\[j]}{c - T\[j]} $$ *** ### Indexed lookup * Claim: $$ (I^\* T)\[i] \stackrel{?}{=} T\[I\[i]] $$ * Example: If $$X = (1,2,1,3,4)$$ and $$T = (1, 2, 3, 4)$$, then in the indexed lookup setting we have $$I = (0,1,0,2,3)$$, so that $$I^\*T = X$$. *** ### Reduction: indexed to non-indexed lookup * Pre-commitment: $$I, T, \textcolor{red}{I^\*T}, \mathsf{acc}$$ * Claim: $$(I^\*T, I) \subseteq (T, \[0, |T|))$$ (or you can say that $$I^\*T$$ is claimed to be pullback) * Challenge: $$c, \gamma$$ * Verification: $$ \sum\_{0 \le i < n}\frac{1}{c - (I^\*T\[i] + \gamma I\[i])} \= \sum\_{0 \le j < m} \frac{\mathsf{acc}\[j]}{c - (T\[j] + \gamma j)} $$ LogUp\* aims to eliminate the need for committing to $$\textcolor{red}{I^\*T}$$ in this reduction. *** ## Protocol Explanation ### Pullback and pushforward #### Notations * $$A: \mathbf{n} = \[0,n) \to \mathbb{F}$$ * $$B: \mathbf{m} = \[0,m) \to \mathbb{F}$$ * $$I: \mathbf{n} \to \mathbf{m}$$ * Pullback: $$ I^\*B\[i] = B\[I\[i]] $$ * Pushforward: $$ I\_\*A\[j] = \sum\_{i \mid I\[i] = j} A\[i] $$ *** #### Lemma 1. Duality $$ \langle I\_\*A, B \rangle = \langle A, I^\*B \rangle $$ **Proof** $$ \langle I\_*A, B \rangle = \sum\_{0 \le j < m} I\_*A\[j]B\[j] \= \sum\_{0 \le j < m}\left(\sum\_{i \mid I\[i] = j} A\[i]\right)B\[j] = \sum\_{0 \le i < n} A\[i]B\[I\[i]] = \langle A, I^\*B \rangle $$ *** **Intuitive example** Let $$A = (1, 2, 1, 3, 4), B = (1, 2, 3, 4), I = (0, 1, 0, 2, 3)$$. Then $$I^\*B = A$$. If $$A = (a\_0, \dots, a\_{n-1})$$, then the right hand is computed as follows: $$ \sum\_{0 \le i < n} a\_i^2 = 1^2 + 2^2 + 1^2 + 3^2 + 4^2 = 31 $$ If $$B = (b\_0, \dots, b\_{m-1})$$, then the left hand is computed as follows: $$ \sum\_{0 \le j < m} \left(\sum\_{i \mid I\[i] = j} a\_i\right)b\_j = (1+1)\cdot 1 + 2\cdot 2 + 3\cdot 3 + 4\cdot 4 = 31 $$ Both sides match, confirming the duality. *** ### Trading pullback for pushforward * Pre-commitment: $$I, T$$ * Claim: $$I^\*T(r) \stackrel{?}{=} e$$ **Protocol** 1. Commit to $$I\_\*\mathsf{eq}\_r$$, where $$ \mathsf{eq}*r(x) = \prod*{0 \le i < k}(r\_i x\_i + (1-r\_i)(1-x\_i)), \quad n < 2^k $$ 2. Observe that $$ I^\*T(r) = \langle I^*T, \mathsf{eq}*r \rangle = \langle T, I** \mathsf{eq}\_r \rangle $$ {% hint style="info" %} Evaluation of a polynomial $$P$$ in a point $$r = (r\_0, \dots, r\_{k−1})$$ can be computed as an inner product with the multilinear Lagrange kernel: $$P(r) = \lang P, \mathsf{eq}\_r \rang$$. {% endhint %} 3. Run sumcheck for the claim $$\langle T, I\_\* \mathsf{eq}*r \rangle \stackrel{?}{=} e$$, obtaining additional evaluation claims $$T(r') \stackrel{?}{=} c, ; I*\*\mathsf{eq}\_r(r') \stackrel{?}{=} c'$$. 4. Open $$T$$ and $$I\_\* \mathsf{eq}\_r$$. This protocol proves the evaluation of $$I^*T(r)$$, provided that $$I\_*\mathsf{eq}\_r$$ was committed correctly. Note that the commitment to $$\textcolor{red}{I^\*T}$$ is not performed. Then we need to check whether $$I\_\*\mathsf{eq}\_r$$ indeed is pushforward. *** ### Pushforward proof with LogUp\* #### General Case * Pre-commitment: $$I, T, X, Y$$ * Claim: $$Y$$is claimed to be pushforward as follows: $$ Y\[j] \stackrel{?}{=} I\_\*X\[j] = \sum\_{i \mid I\[i] = j} X\[i] $$ * Challenge: $$c$$ * Verification: $$ \sum\_{0 \le i < n} \frac{X\[i]}{c - I\[i]} = \sum\_{0 \le j < m} \frac{Y\[j]}{c - j} $$ Intuitively, if $$I\[i = 1,5,7] \mapsto j=3$$, then the left-hand side contributes $$\frac{X\[1] + X\[5] + X\[7]}{c-3}$$, while the right-hand side uses $$\frac{Y\[3]}{c-3}$$ to represent the same value. *** #### Our Case * Pre-commitment: $$I, T, Y$$ (here $$X = \mathsf{eq}\_r$$, and since the verifier can compute $$\mathsf{eq}\_r$$ directly, there is no need to commit to $$X$$). * Challenge: $$c$$ * Verification: $$ \sum\_{0 \le i < n}\frac{\mathsf{eq}*r\[i]}{c - I\[i]} \= \sum*{0 \le j < m} \frac{I\_\*\mathsf{eq}\_r\[j]}{c - j} $$ Thus, the prover only commits to $$I, T, Y$$, while the verifier computes $$\mathsf{eq}\_r$$ on its own to complete the verification. ## References * > Written by [Ryan Kim](mailto:undefined) of Fractalyze --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://fractalyze.gitbook.io/intro/zk/lookup/logup.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.