# LogUp\* ## Introduction [LogUp](https://fractalyze.gitbook.io/intro/~/revisions/WK2i8xxbUNf7f7bV0E9h/zk/logup-gkr#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](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze