# Dynamic lookups

## Example

Assume the following circuit layout:
- Four columns $A, B, C, D$ used to store arbitrary dynamic tables, where the unused rows can be used for general constraints but not table lookups.
- A fixed column $tag$ generated and filled by the backend.
- Three columns $E, F, G$ that do _not_ store any table data, and are just regular advice / fixed columns for regular circuit variables.
- A selector-like column $U$ used to control which table an input is looked up in.
- In the simple case, this would just be a fixed column; this allows dynamic _table contents_, but not _table shape_ or _table access_.
- If we also allow $U$ to be an advice column, then we also allow dynamic _table access_: every row could look up any table, or no table.
- There is a potential hazard in that if $U_i$ is not a valid table tag, then the behaviour is undefined. We could probably make this always a constraint failure at no extra cost.
- For dynamic _table shape_, you'd need to fake it by defining a larger table shape than needed, and fill in sub-areas.

$$
\begin{array}{|c|c|c|c|c|c|}
tag & A & B & C & D & E & F & G & U \\\hline
1 & a_0 & a_1 & - & - & a_2 & a_3 & - & 1 \\
1 & a_2 & a_3 & - & - & a_4 & a_5 & a_6 & 2 \\
2 & - & a_4 & a_5 & a_6 & - & - & - & 0 \\
2 & - & a_7 & a_8 & a_9 & - & - & - & 0 \\
0 & - & - & - & - & - & - & - & 0
\end{array}
$$

We have a lookup argument of the form $S \in T$, where $\theta$ is a random challenge.

$$
S = \begin{cases}
U_i, &\text{if } U_i = 0 \\
U_i + \theta E_i + \theta^2 F_i, &\text{if } U_i = 1 \\
U_i + \theta E_i + \theta^2 F_i + \theta^3 G_i, &\text{if } U_i = 2 \\
\end{cases}
$$
$$
T = \begin{cases}
tag_i, &\text{if } tag_i = 0 \\
tag_i + \theta A_i + \theta^2 B_i, &\text{if } tag_i = 1 \\
tag_i + \theta B_i + \theta^2 C_i + \theta^3 D_i, &\text{if } tag_i = 2 \\
\end{cases}
$$

The backend tracks $U$, and once all regions have been assigned, the backend applies equality constraints to constrain all $U_i$ outside a defined region to be $0$.

### Optimizations

- In the [Lagrange interpolation](https://en.wikipedia.org/wiki/Lagrange_polynomial), the denominator is the same on each side and so isn't needed in the polynomial constraints.
- If the same columns are used for all lookups, then we can simplify S.
- If the same columns are used for all tables, then we can simplify T.

### Restrictions

- The $tag$ and $U$ columns must be assigned for all rows (like selectors are).
- There must exist at least one row where $tag = 0$ (to effectively define the "zero table" that otherwise doesn't exist).

## Generalising to allow lookups underneath tables

Now assume the following circuit layout:
- Four columns $A, B, C, D$ used to store arbitrary dynamic tables, where their unused row space can _also_ be used for table lookups.
- A fixed column $tag$ generated and filled by the backend.
- A selector-like column $U$ used to control which table an input is looked up in.

$$
\begin{array}{|c|c|c|c|c|c|}
tag & A & B & C & D & U \\\hline
1 & a_0 & a_1 & - & - & 0 \\
1 & a_2 & a_3 & - & - & 0 \\
2 & - & a_4 & a_5 & a_6 & 0 \\
2 & - & a_7 & a_8 & a_9 & 0 \\
0 & - & - & - & - & 0 \\
0 & a_2 & a_3 & - & - & 1 \\
0 & a_4 & a_5 & a_6 & - & 2
\end{array}
$$

We have a lookup argument of the form $S \in T$, where $\theta$ is a random challenge.

$$
S = \begin{cases}
U_i, &\text{if } U_i = 0 \\
U_i + \theta A_i + \theta^2 B_i, &\text{if } U_i = 1 \\
U_i + \theta A_i + \theta^2 B_i + \theta^3 C_i, &\text{if } U_i = 2 \\
\end{cases}
$$
$$
T = \begin{cases}
tag_i, &\text{if } tag_i = 0 \\
tag_i + \theta A_i + \theta^2 B_i, &\text{if } tag_i = 1 \\
tag_i + \theta B_i + \theta^2 C_i + \theta^3 D_i, &\text{if } tag_i = 2 \\
\end{cases}
$$

> $i$ is the absolute row number.

TODO: prove that it's okay to not constrain $U_i$ to be in range (a valid table tag). Alternatively, if $U$ is required by the API to be a fixed column, there is no issue.

### Additional restriction

- $tag_i \neq U_i$ for the same $i$ (otherwise we'd be constraining a lookup of a table's contents into itself, which allows that row to be unconstrained, and is also confusing). The backend / APIs would enforce this.
> Are there no valid cases there $tag_i = U_i$? Also, will the constraint system enforce this? ^ [name=ying tong]

- In the regular region API, we'd need to require at least one of $tag_i$ or $U_i$ to be non-zero for the same $i$. This is because the "table regions" and "constraint region" cannot overlap by definition.
- However, there may be potential use cases for constraining that some subset of the contents of a table is present in another table. This _could_ potentially be allowed as part of the table definition API that assigns the "table regions".
- We should probably not do this in the first iteration (as it would need a new API anyway, and can always be simulated by using equality constraints). Omit it to start, and open an issue describing it, to allow people to comment with their use cases.