Investigate lookup optimization for tables of small values

[mimoo]

Copying this TODO (with a few formatting changes) from the code, which I believe @imeckler wrote

Looking-up a tuple (f_0, f_1, ..., f_{m-1}) in a tuple of tables (T_0, ..., T_{m-1}) is reduced to a single lookup

sum_i joint_combiner^i f_i

in the "joint table"

sum_i joint_combiner^i T_i

We write down all these combined joint lookups in the sorted-lookup table, so lookup_sorted ends up being a list of all these combined values.

We will commit to the columns of lookup_sorted. For example, the 0-th one, as

sum_i lookup_sorted[0][i] * L_i

where L_i is the i-th normalized lagrange commitment, and where

lookup_sorted[0][i] = sum_j joint_combiner^j f_{0, i, j}

for some lookup values f_{0, i, j}

Computing it that way is not the best, since for example, in our four-bit xor table, all the individual f_{0, i, j} are only four bits while the combined scalar

sum_j joint_combiner^j f_{0, i, j}

will (with overwhelming probability) be a basically full-width field element.

As a result, if the lookup values are smaller, it will be better not to combine the joint lookup values and instead to compute the commitment to lookup_sorted[0][i] (for example) as

sum_j joint_combiner^j (sum_i f_{0, i, j} L_i)
= sum_i (sum_j joint_combiner^j f_{0, i, j}) L_i
= sum_i lookup_sorted[0][i] L_i

This should be quite a lot cheaper when the scalars f_{0, i, j} are small. We should try it to see how it is in practice. It would be nice if there were some cheap computation we could run on the lookup values to determine whether we should combine the scalars before the multi-exp or not, like computing their average length or something like that.

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message