# Another approach to BDSC ("Vector Commit and Prove") from Lookups

Idea by Carla.

Goal: Let $I$ be a set of indices the verifier wants to look up in a vector (in a subvector opening sense). We want to reduce this to a lookup. The tiny challenge is making sure that those indices are used correctly by the prover (since a lookup argument in general just throws indices out of the window)

Notation:
- we denote by $[T]$ a table, that is any preprocessed column vector we will lookup *into*.

Setting:
- Both P and V share two column tables:
- $[idx] = (1,2,3,\dots)$, just the natural numbers till $N$
- $[V] = (v_1, v_2, \dots)$, the actual vector we want to prove opening into

## The protocol
- P sends $c_I = Com(I)$ where this commitment is done in a normalized basis.
- The protocol then consists of two parts.
---
- For the subvector opening:
- P sends commitment to sub vector of claimed values $C_{subv} = Com((v_i)_{i\in I})$
- V sends challenge $\alpha$
- P and V make online table $[T'] = \alpha[idx] + [V]$ and lookup commitment $C' = \alpha C_I + C_{subv}$
- They run a lookup on $[T'], C'$

---
For checking relation to actual subset of interest:
- V samples $r \gets \mathbb{F}$
- V computes $y = p_I(r)$ where $p_i$ is the interpolating polynomial of set $I$
- V sends a proof of poly evaluation that the polynomial committed in $C_I$ actually evaluates to $y$, which V checks