# RAMLookup: Simulating random-access memory in zero-knowledge proofs
###### Author: Matthew Ryan

Recent developments in zero-knowledge (ZK) proof systems have brought private, verifiable computing closer than ever to traditional computing, unlocking even more potential applications and bringing more flexibility to developers. The introduction of 'lookup arguments' has been a key piece of this puzzle, and the ecosystem has seen accelerating progress.

In this post we outline why lookup arguments are useful, some history of the development of lookup arguments, and describe our new RAMLookup protocol for faithfully simulating Random-Access Memory (RAM) in zero-knowledge.

## Lookup arguments

### Background

ZK proof systems differ from traditional computers in a fundamental way: instead of using bits and bytes, with the familiar logic gates (`AND`,`OR`,`XOR`, `NOT`, etc.), ZK proofs (ZKPs) use 'finite field elements' and the arithmetic operations `ADD` and `MUL`, along with `ASSERT_EQUAL`. This means that some things that are very efficient for tranditional computers, like checking that the result of an addition fits in 8 bits, or XOR-ing 2 8-bit numbers, are significantly more expensive in ZKPs.

The goal of **lookup arguments** is to address some of these shortcomings. As we will explore, there is even more potential to move closer to traditional computing, which we at O(1) Labs have been working to unlock.

### What is a lookup argument, and how does it help?

A lookup argument is a small cryptographic part of a larger ZK proof system which, given a list of values `Table`, lets you check that some other values in the proof match one of those values in `Table`.

In the abstract, you can think of this like a function `assert_in_table` that you can include in a ZKP, which behaves like:

function assert_in_table(table, x) {
  for (entry in table) {
    if (entry == x) {
      return;
    }
  }
  throw Error("Not in table");
}

For the simplest example above -- checking that the result of an addition fits in 8 bits -- we can fill our `Table` with the numbers `0`, `1`, ..., `255` and use `assert_in_table(Table, x)` to confirm that our value `x` does indeed fit into 8 bits. In the literature, such a check is called a 'range check'. Notice that in this example the number of entries in our `Table` corresponds to $2^8$.

#### Simulating functions with lookup tables

A more interesting example is `XOR`ing 2 8-bit numbers. What we would like to do is look up three values at once: the `left_input`, the `right_input` and the `output`. If we can look up multiple values in the same 'entry' in the table, then we could create a `Table` with entries corresponding to each of the possible inputs and outputs of XOR that we want to support.

(0, 0, 0)
(0, 1, 1)
(0, 2, 2)
...
(1, 0, 1)
(1, 1, 0)
...
(255, 254, 1)
(255, 255, 0)

| left_input | right_input | output |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 2 | 2 |
| ... | ... | ... |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| ... | ... | ... |
| 255 | 254 | 1 |
| 255 | 255 | 0 |

Since lookup arguments only operate on a single value, we need a clever trick to combine them into a single value. In principle, we can just combine the inputs and outputs by adding them together:

value_to_lookup =
  something_1 * left_input + something_2 * right_input + something_3 * output

Which is efficient to do in the snark. However, we need to make sure that the prover can't cheat and use different values! For example, if we choose:

something_1 = 1
something_2 = 2^8
something_3 = 2^16

Then, a valid lookup of `(15, 1, 14)` representing `15 XOR 1 = 14` will result in a lookup of value `15 + 1 * 256 + 14 * 65536 = 917775`; but a malicious prover could choose the values `(271, 0, 14)` which also encodes the value `271 + 0 * 256 + 14 * 65536 = 917775`. In this scenario, the prover would be able to prove an invalid `XOR` operation as valid since `271 XOR 0` equals to `271`, not `14`.

Instead, we use the Fiat-Shamir trick, by making the prover commit to the values that they want to look up before they find out what the `something_i` values are. We can hash those commitments to generate a random number `random_mixer` and set:

something_1 = random_mixer^0
something_2 = random_mixer^1
something_3 = random_mixer^2

Since we choose the value `random_mixer` after the values to look up have already been decided, a malicious prover cannot choose values outside of the table that will result in a value from inside the table!

This has the effect of changing `assert_in_table` to:

function assert_in_table(table, x) {
  var value_to_lookup = 0;
  var mixer = 1;
  for (value in x) {
    value_to_lookup += mixer * value;
    mixer *= random_mixer;
  }
  for (entry in table) {
    if (entry == value_to_lookup) {
      return;
    }
  }
  throw Error("Not in table");
}

Where looking up a single value is `assert_in_table(Table, [x])` (like we did for the range check example), and looking up our 3 values for `XOR` looks like `assert_in_table(Table, [left_input, right_input, output])`.

We can do the same trick with the values in the table, generating:

Table[i] =
    random_mixer^0 * FirstTableEntry[i]
  + random_mixer^1 * SecondTableEntry[i]
  + random_mixer^2 * ThirdTableEntry[i]

And then `assert_in_table` can be used to simulate XOR using our precomputed table above.

#### Using multiple lookup tables in a single lookup argument

We've shown that you can use a lookup table to perform a 'range check' *or* to simulate some function. However, it would be helpful -- and make the proof smaller -- if we could use the same lookup argument to perform the lookups that we need for both of these different lookups.

Considering our examples, we have 2 tables: 8-bit range check and `XOR`. What we would really like to do is add a way to combine them into a single table, and give the lookups (calls to `assert_in_table`) in the proof a way to specify which table out of the combined table they would like.

If we naively join the tables together, adding `0` for values that we aren't going to use, we get the width-3 table

FirstTableEntry | SecondTableEntry | ThirdTableEntry
----------------+------------------+----------------
/* 8-bit range check part */
0               | 0                | 0
1               | 0                | 0
2               | 0                | 0
...             | ...              | ...
255             | 0                | 0
/* XOR part */
0               | 0                | 0
0               | 1                | 1
...             | ...              | ...
1               | 0                | 1
1               | 1                | 0
...             | ...              | ...
255             | 254              | 1
255             | 254              | 0

This works perfectly for our range-check lookup, but now we have an issue with XOR: a malicious prover could run `assert_in_table(Table, [3, 0, 0])` and claim that `3 XOR 0 = 0` using the value from the range-check table!

Luckily, the solution is simple: we can give each individual table an ID, treating it as an column in the table, and use the same trick as before:

Table ID | FirstTableEntry | SecondTableEntry | ThirdTableEntry
---------+-----------------+------------------+----------------
/* 8-bit range check part */
0        | 0               | 0                | 0
0        | 1               | 0                | 0
0        | 2               | 0                | 0
...      | ...             | ...              | ...
0        | 255             | 0                | 0
/* XOR part */
1        | 0               | 0                | 0
1        | 0               | 1                | 1
...      | ...             | ...              | ...
1        | 1               | 0                | 1
1        | 1               | 1                | 0
...      | ...             | ...              | ...
1        | 255             | 254              | 1
1        | 255             | 254              | 0

Now, our `assert_in_table` looks like:

function assert_in_table(table, table_id, x) {
  var value_to_lookup = table_id;
  var mixer = random_mixer;
  for (value in x) {
    value_to_lookup += mixer * value;
    mixer *= random_mixer;
  }
  for (entry in table) {
    if (entry == value_to_lookup) {
      return;
    }
  }
  throw Error("Not in table");
}

so that our new `assert_in_table(Table, ID, [a, b, c])` is the same as doing `assert_in_table(Table, [ID, a, b, c])` with the old `assert_in_table`.

Finally, we have all the pieces to convert complex or expensive operations into cheaper lookups, allowing us to create smaller, more efficient ZKPs.

### Okay but... how does it actually work?

As we mentioned above, ZKPs only have 3 building blocks: `ADD`, `MUL`, and `ASSERT_EQUAL`. Using just these operations, we want to find a way to compare the values looked up in the circuit to the values that we're allowed to look up.

A nice way to reason about lookup arguments is to think about them as a pair of mathematical 'bags of numbers'. Into `bag_1`, we want to put all of the values that we look up, and into `bag_2` we want to put all of the values that we are *allowed* to look up, determined by the table.

Different lookup arguments behave in different ways, but they all share 4 basic operations:
* `empty_bag` returns an empty bag, so that we can start from a known state;
* `add_to_bag` adds a value to the bag for every value in the table, or for every step of the ZKP that uses a lookup;
* `same_bags_value` is a fixed value;
* `compare_bags` takes 2 bags and returns `same_bags_value` if the two bags contain the same values.

In the protocols that we will explore, instead of tracking the bags individually, we track an 'accumulator' `acc` as we proceed through the proof, which contains the value of `compare_bags` after every step. Therefore we have:

bag_1[0] = empty_bag
bag_2[0] = empty_bag
... /* Add some things to each bag */
compare_bags(bag_1[n], bag_2[n]) = same_bags_value

where `n+1` is total number of bags, with `bag_1[n]` and `bag_2[n]` being the final state of `bag_1` and `bag_2` respectively.

Reducing this to the accumulator:

acc[0] = same_bags_value
acc[i] = compare_bags(bag_1[i], bag_2[i])
acc[n] = same_bags_value

## The plonk permutation argument

In the sense described above, the 'permutation argument' described in the plonk paper is not a *true* lookup argument: it asserts that values from different parts of the ZKP are equal to *each other*, but it doesn't allow for a lookup table that the values must come from. Nonetheless, the permutation argument was an important step in the development of lookup arguments in general.

### The general idea

The permutation argument starts with the idea that every value in a ZKP can be laid out in a 2D grid, like so:

y   x | 1   | 2   | 3   | 4   | ... | k
------+-----+-----+-----+-----+-----+-----
1     | ?   | ?   | ?   | ?   | ... | ?
2     | ?   | ?   | ?   | ?   | ... | ?
3     | ?   | ?   | ?   | ?   | ... | ?
4     | ?   | ?   | ?   | ?   | ... | ?
...   | ... | ... | ... | ... | ... | ...
n     | ?   | ?   | ?   | ?   | ... | ?

If we associate every value with its coordinates in the grid, we can turn this into a long list

(1, 1, ?)
(1, 2, ?)
...
(1, k, ?)
(2, 1, ?)
...
(n, k, ?)

that we can iterate over to run the permutation argument.

At this stage, we can decide which values we want to be equal, and group the coordinates into groups that all must have the same value. For example, if we want the values at `(1, 1)`, `(2, 2)` and `(4, 3)` to be equal, we create the list `[(1, 1), (2, 2), (4, 3)]`; if we don't need the value at `(1, 2)` to equal any others, then we can put it in its own group `[(1, 2)]`.

We should now have every coordinate at exactly one position of exactly one list. We can now take each list `l`, copy it, and rotate it by 1 position to
the left to get `l_shifted`. For example:

l         = [(1, 1), (2, 2), (4, 3)]
l_shifted = [(2, 2), (4, 3), (1, 1)]

Now, the idea is that we put each value into `bag_1` with its coordinates, and we put that value into `bag_2` with the value from `l_shifted` that matches its coordinates. In terms of our example, this looks like:

add_to_bag(bag_1, (1, 1, x_1_1)) /* add x_1_1 at its coordinate */
add_to_bag(bag_1, (2, 2, x_2_2)) /* add x_2_2 at its coordinate */
add_to_bag(bag_1, (4, 3, x_4_3)) /* add x_4_3 at its coordinate */

add_to_bag(bag_2, (2, 2, x_1_1)) /* add x_1_1 as if it was at (2, 2) */
add_to_bag(bag_2, (4, 3, x_2_2)) /* add x_2_2 as if it was at (4, 3) */
add_to_bag(bag_2, (1, 1, x_4_3)) /* add x_4_3 as if it was at (1, 1) */

and then the argument can only succeed if `x_1_1 = x_2_2 = x_4_3`, otherwise the bags will have different values.

### As a 'lookup argument'

The permutation argument is a 'multiplicitive' argument, which means that we multiply together a value related to every element in each bag, and we compare the bags by dividing them.

In terms of our operations above, the protocol is essentially:

empty_bag = 1
add_to_bag(bag, (x, y, value)) =
    bag * (value + mixer_1 * x + mixer_2 * y + mixer_3)
same_bags_value = 1
compare_bags(bag1, bag2) = bag1 / bag2

We use 3 `mixer` values as part of the protocol, which can be chosen using Fiat-Shamir as described above to stop a malicious prover from cheating.

Importantly, using random values also makes sure that the probability of multiplying by 0 is negligible -- about `1/2^255` for Kimchi proofs.

### Rolling it out in Kimchi

One quirk of Kimchi's proof system is that we cannot multiply more than 8 variables (or, more technically, polynomials) in a single constraint. Similar constraints apply to other proof systems, e.g. pairing-based ZKPs, where this number is even lower at 2!

This guides us to our first design decision: at each step of the ZKP, we include the first 7 'columns' of variables in the permutation argument. As constraints, we have:

/* At step 1 */
acc[0] = 1
/* At steps 1 to n */
acc[i+1] =
    acc[i]
  * (column[0][i] + mixer_1 * 0 + mixer_2 * i + mixer_3)
  * (column[1][i] + mixer_1 * 1 + mixer_2 * i + mixer_3)
  * (column[2][i] + mixer_1 * 2 + mixer_2 * i + mixer_3)
  * (column[3][i] + mixer_1 * 3 + mixer_2 * i + mixer_3)
  * (column[4][i] + mixer_1 * 4 + mixer_2 * i + mixer_3)
  * (column[5][i] + mixer_1 * 5 + mixer_2 * i + mixer_3)
  * (column[6][i] + mixer_1 * 6 + mixer_2 * i + mixer_3)
  / (
      (column[0][i] + mixer_1 * permut_x[0][i] + mixer_2 * permut_y[0][i] + mixer_3)
    * (column[1][i] + mixer_1 * permut_x[1][i] + mixer_2 * permut_y[1][i] + mixer_3)
    * (column[2][i] + mixer_1 * permut_x[2][i] + mixer_2 * permut_y[2][i] + mixer_3)
    * (column[3][i] + mixer_1 * permut_x[3][i] + mixer_2 * permut_y[3][i] + mixer_3)
    * (column[4][i] + mixer_1 * permut_x[4][i] + mixer_2 * permut_y[4][i] + mixer_3)
    * (column[5][i] + mixer_1 * permut_x[5][i] + mixer_2 * permut_y[5][i] + mixer_3)
    * (column[6][i] + mixer_1 * permut_x[6][i] + mixer_2 * permut_y[6][i] + mixer_3) )
/* At step n */
acc[n+1] = 1

However, notice that we also never said that we could do divisions -- a common factor between ZK proof systems. Instead, we tweak our second constraint so
that it uses only multiplications:

acc[i+1]
  * (column[0][i] + mixer_1 * permut_x[0][i] + mixer_2 * permut_y[0][i] + mixer_3)
  * (column[1][i] + mixer_1 * permut_x[1][i] + mixer_2 * permut_y[1][i] + mixer_3)
  * (column[2][i] + mixer_1 * permut_x[2][i] + mixer_2 * permut_y[2][i] + mixer_3)
  * (column[3][i] + mixer_1 * permut_x[3][i] + mixer_2 * permut_y[3][i] + mixer_3)
  * (column[4][i] + mixer_1 * permut_x[4][i] + mixer_2 * permut_y[4][i] + mixer_3)
  * (column[5][i] + mixer_1 * permut_x[5][i] + mixer_2 * permut_y[5][i] + mixer_3)
  * (column[6][i] + mixer_1 * permut_x[6][i] + mixer_2 * permut_y[6][i] + mixer_3)
=   acc[i]
  * (column[0][i] + mixer_1 * 0 + mixer_2 * i + mixer_3)
  * (column[1][i] + mixer_1 * 1 + mixer_2 * i + mixer_3)
  * (column[2][i] + mixer_1 * 2 + mixer_2 * i + mixer_3)
  * (column[3][i] + mixer_1 * 3 + mixer_2 * i + mixer_3)
  * (column[4][i] + mixer_1 * 4 + mixer_2 * i + mixer_3)
  * (column[5][i] + mixer_1 * 5 + mixer_2 * i + mixer_3)
  * (column[6][i] + mixer_1 * 6 + mixer_2 * i + mixer_3)

NB: We have switched to 0-based indexing to match the Kimchi implementation more closely; the protocol works equivalently with 1-based indexing, as in the explainer above!

TODO: Costs in terms of columns

## The plookup argument

This is our first 'real' lookup argument, which allows us to 'load' a table into the proof from which we can look up values. This represented a seismic shift in ZKPs, opening the potential for simulating other architectures cheaply with the function model, and starting progress towards the more conventional 'memory' model of traditional computing.

### The general idea

The plookup argument uses the structure of the lookup table to make guarantees about which values 'come from' the table vs which values have been 'looked up' as part of the ZKP. Since the values form a list, we can use the difference
between each value and the next to detect whether they the value is repeated.

In effect, we place the pair `(Table[i], Table[i+1])` into the bag. For example, consider our 8-bit range check table from before, with the final value repeated:

Entry | Difference
------+-----------
0     | 1
1     | 1
2     | 1
...   | ...
254   | 1
255   | 0
255   | -

If we lookup several values in the table, and encode these by repeating the corresponding entries in their original position, we can see that we preserve the values in the bag, and only introduce new values whose difference is 0:

Entry | Difference
------+-----------
0     | 0 /* Lookup of 0 */
0     | 0 /* Lookup of 0 */
0     | 1
1     | 1
2     | 0 /* Lookup of 2 */
2     | 0 /* Lookup of 2 */
2     | 0 /* Lookup of 2 */
2     | 1
...   | ...
254   | 0 /* Lookup of 254 */
254   | 1
255   | 0
255   | -

Once we have built our 'witness' for the ZKP, we know which values we have been looked up, so we can build a list like this second table which includes them in the correct order (according to the original table's order). We will call this list `SortedTable`.

Therefore, in `bag_1` we can insert:
* `(Table[i], Table[i+1])` for each `i`, and
* `(lookup_value, 0)` for each `lookup_value` looked up in a step of the ZKP.

Correspondingly, in `bag_2` we can insert:
* `(SortedTable[i], SortedTable[i+1])` for each `i`.

Once again, the argument can only work if the values in `bag_1` exactly match the values in `bag_2`, so we know that:
* every value `Table[i]` has an equal value `SortedTable[j]`, where
`Table[i+1] = SortedTable[j+1]`
* every `lookup_value` has a unique `j` such that
`SortedTable[j] = SortedTable[j+1] = lookup_value`.

### As a lookup argument

Once again, the plookup argument is a 'multiplicitive' argument.

In terms of our operations above, the protocol is essentially:

empty_bag = 1
add_to_bag(bag, (value, difference)) =
    bag * (value * (1 + mixer_1) + difference * mixer_1)
same_bags_value = 1
compare_bags(bag1, bag2) = bag1 / bag2

As before, we use Fiat-Shamir to select `mixer_1` after the prover has committed to their lookups, to prevent cheating.

The `add_to_bag` function here is a little more interesting: when we are adding to the bag from one of the tables -- either `Table` or `SortedTable` -- we can cancel out the `-value` in the difference; otherwise, when it is 0, we can factor out the `1 + mixer_1` term. Concretely:

add_to_bag(bag, (tbl[i], tbl[i+1])) = bag * (tbl[i] + mixer_1 * tbl[i+1])
add_to_bag(bag, (value, 0)) = bag * (1 + mixer_1) * value 

### Rolling it out in Kimchi

Due to the same quirk as before, we are limited in the number of lookups that any constraint can integrate in Kimchi. Due to some other overheads, we chose to support a maximum of 4 lookups at each step.

The constraints look suspiciously similar to the permutation argument's, except we use a placeholder `lookup_value[i][j]` variable that gets replaced with a concrete expression depending on what the current step of the ZKP is doing.

Note also that we split `SortedTable` into several chunks, to allow us to run the argument all at once.

/* At step 1 */
acc[0] = 1
/* At steps 1 to n */
acc[i+1] =
    acc[i]
  * (lookup_value[0][i] + (1 + mixer_1))
  * (lookup_value[1][i] + (1 + mixer_1))
  * (lookup_value[2][i] + (1 + mixer_1))
  * (lookup_value[3][i] + (1 + mixer_1))
  * (Table[i] + mixer_1 * Table[i+1])
  / (
      (SortedTable[0][i] + mixer_1 * SortedTable[0][i+1])
    * (SortedTable[1][i] + mixer_1 * SortedTable[1][i+1])
    * (SortedTable[2][i] + mixer_1 * SortedTable[2][i+1])
    * (SortedTable[3][i] + mixer_1 * SortedTable[3][i+1])
    * (SortedTable[4][i] + mixer_1 * SortedTable[4][i+1]) )
/* At step n */
acc[n+1] = 1

Once again, we tweak the accumulator constraint so that it can be expressed in terms of multiplication:

acc[i+1]
  * (SortedTable[0][i] + mixer_1 * SortedTable[0][i+1])
  * (SortedTable[1][i] + mixer_1 * SortedTable[1][i+1])
  * (SortedTable[2][i] + mixer_1 * SortedTable[2][i+1])
  * (SortedTable[3][i] + mixer_1 * SortedTable[3][i+1])
  * (SortedTable[4][i] + mixer_1 * SortedTable[4][i+1]) )
=   acc[i]
  * (lookup_value[0][i] + (1 + mixer_1))
  * (lookup_value[1][i] + (1 + mixer_1))
  * (lookup_value[2][i] + (1 + mixer_1))
  * (lookup_value[3][i] + (1 + mixer_1))
  * (Table[i] + mixer_1 * Table[i+1])

NB: We have switched to 0-based indexing to match the Kimchi implementation
more closely; the protocol works equivalently with 1-based indexing, as in the
explainer above!

TODO: Costs in terms of columns

## The MVLookup argument

MVLookup is a recent development in lookup arguments, which switches to an 'additive' argument rather than a multiplicitive one. As we shall explore below, the additive nature of this argument brings us the possibility of removing elements from our bags as well as inserting them, which brings us still closer to our goal of a read-write memory primitive.

### The general idea

In some senses, this is the simplest of the arguments we have looked at so far. Every value contributes `1/(mixer + lookup_value)`, and we can scale each of the lookup table's values's contributions by the number of times they are looked up. This gives us the protocol:

  1/(mixer_1 + lookup_value[0])
+ 1/(mixer_1 + lookup_value[1])
+ 1/(mixer_1 + lookup_value[2])
+ ...
+ 1/(mixer_1 + lookup_value[k])
= num_uses[0]/(mixer_1 + Table[0])
+ num_uses[1]/(mixer_1 + Table[1])
+ num_uses[2]/(mixer_1 + Table[2])
+ ...
+ num_uses[n]/(mixer_1 + Table[n])

The use of inversion (i.e. `1/something`) along with addition ensures that any change to *any* lookup value will affect *all* of the other additive terms in an unpredictable way: multiplying through by all of the denominators gives us`(mixer_1 + lookup_value)` as a term multiplied by all of the additive terms
except its own one.

### As a lookup argument

In terms of our operations from before, the protocol is essentially:

empty_bag = 0
add_to_bag(bag, (value, difference)) = bag + 1 / (mixer_1 + value)
same_bags_value = 0
compare_bags(bag1, bag2) = bag1 - bag2

Once again, we ensure that the values looked-up can't be chosen maliciously by using Fiat-Shamir to select `mixer_1` after the lookups have already been committed to by the prover.

As noted above: instead of repeatedly adding a single value from the table using `add_to_bag`, we can use multiplication to perform as many (or no) additions as needed, in a single step.

### Rolling it out in Kimchi

Since this argument is additive, we have a lot more flexibility in Kimchi, since it appears that we don't have the same cost in computing the accumulator.

/* At step 1 */
acc[0] = 1
/* At steps 1 to n */
acc[i+1] =
    acc[i]
  + 1 / (mixer_1 + lookup_value[0][i])
  + 1 / (mixer_1 + lookup_value[1][i])
  + 1 / (mixer_1 + lookup_value[2][i])
  + ...
  + 1 / (mixer_1 + lookup_value[k][i])
  - NumUses[i] / (mixer_1 + Table[i])
/* At step n */
acc[n+1] = 1

However, we *still* don't have a native inversion / division operation, so we have to do some multiplications. Happily, even with this design constraint, we can look up more values at a much lower cost, by using some intermediate variables to help with these inversions:

inversion_sum[i][0] =
    1 / (mixer_1 + lookup_value[0][i])
  + 1 / (mixer_1 + lookup_value[1][i])
  + 1 / (mixer_1 + lookup_value[2][i])
  + ...
  + 1 / (mixer_1 + lookup_value[5][i])
inversion_sum[i][1] =
    1 / (mixer_1 + lookup_value[6][i])
  + 1 / (mixer_1 + lookup_value[7][i])
  + 1 / (mixer_1 + lookup_value[8][i])
  + ...
  + 1 / (mixer_1 + lookup_value[11][i])
...
inversion_sum[i][k] =
    1 / (mixer_1 + lookup_value[6k][i])
  + 1 / (mixer_1 + lookup_value[6k+1][i])
  + 1 / (mixer_1 + lookup_value[6k+2][i])
  + ...
  + 1 / (mixer_1 + lookup_value[6k+5][i])
acc[i+1] =
    acc[i]
  + inversion_sum[i][0]
  + inversion_sum[i][1]
  + ...
  + inversion_sum[i][k]

Multiplying through by the denominators, we get:

inversion_sum[i][j]
* (mixer_1 + lookup_value[6j][i])
* (mixer_1 + lookup_value[6j+1][i])
* (mixer_1 + lookup_value[6j+2][i])
* (mixer_1 + lookup_value[6j+3][i])
* (mixer_1 + lookup_value[6j+4][i])
* (mixer_1 + lookup_value[6j+5][i])
= 
      (mixer_1 + lookup_value[6j+1][i])
    * (mixer_1 + lookup_value[6j+2][i])
    * (mixer_1 + lookup_value[6j+3][i])
    * (mixer_1 + lookup_value[6j+4][i])
    * (mixer_1 + lookup_value[6j+5][i])
  +   (mixer_1 + lookup_value[6j][i])
    * (mixer_1 + lookup_value[6j+2][i])
    * (mixer_1 + lookup_value[6j+3][i])
    * (mixer_1 + lookup_value[6j+4][i])
    * (mixer_1 + lookup_value[6j+5][i])
  +   (mixer_1 + lookup_value[6j][i])
    * (mixer_1 + lookup_value[6j+1][i])
    * (mixer_1 + lookup_value[6j+3][i])
    * (mixer_1 + lookup_value[6j+4][i])
    * (mixer_1 + lookup_value[6j+5][i])
  +   (mixer_1 + lookup_value[6j][i])
    * (mixer_1 + lookup_value[6j+1][i])
    * (mixer_1 + lookup_value[6j+2][i])
    * (mixer_1 + lookup_value[6j+4][i])
    * (mixer_1 + lookup_value[6j+5][i])
  +   (mixer_1 + lookup_value[6j][i])
    * (mixer_1 + lookup_value[6j+1][i])
    * (mixer_1 + lookup_value[6j+2][i])
    * (mixer_1 + lookup_value[6j+3][i])
    * (mixer_1 + lookup_value[6j+5][i])
  +   (mixer_1 + lookup_value[6j][i])
    * (mixer_1 + lookup_value[6j+1][i])
    * (mixer_1 + lookup_value[6j+2][i])
    * (mixer_1 + lookup_value[6j+3][i])
    * (mixer_1 + lookup_value[6j+4][i])

Notice that, as opposed to plookup where we had to create an extra column of `SortedTable` for every value that we look up in each step of the ZKP, here we only pay with an extra column after 6 more column!

TODO: Costs in terms of columns

## RAMLookup: Adapting RAMLookup for random access memory

TODO