Consensys
feat: add lookup table
Adds AS-Waksman permutation network (for internal use only for building gadgets).
We implement a simple append-only lookup table using it. We could probably also to a full RW memory possibly.
Thoughts:
- [ ] right now we use simplified form of RAM, which requires switching also indices and prev-values. If the actual values are smaller (for example when switching the limbs of non-native elements), then we could pack everything into a single variable and use more efficient switching.
- [ ] otherwise, if we would want to lookup from arrays, we can have more efficient switching if we consider the whole array at once.
- [ ] it would be rally easy to extend this approach to proper RAM. Maybe should add now?
- [ ] the entries do not have to be consecutively ordered. Right now we use curr_index-prev_index to indicate if we should compare against current or previous but could use IsZero(curr_index-prev_index). It is only one constraint more.
Actually, all these things seem to be something which could be provided as initialisation options. Maybe makes sense to implement that way?
Does this implement a particular paper?
The AS Waksman routing network is described in On Arbitrary Waksman Networks and their Vulnerability by Beauquier and Darrot. It describes how to connect the gates in layers, the tricks for the lower gates and splitting to obtain the arbitrary-sizeness (compared to previous results where the number of inputs had to be power of two). It also describes bipartite coloring for deciding the routing.
Oh - I liked the PR, but there is probably no need for it anymore when we have a lot more efficient methods. It didn't work well neither.