Deliver dynamic arrays

[Trivo25]

Pick up #1848 and release it

• bring up to date with the latest o1js/main (should be easy)
• integrate runtime tables for efficiency
  • TBD how
• review and merge

[querolita]

Update:

• Started drafting ideas about where to use runtime tables for the dynamic arrays support

[querolita]

Ideas

Background

• Runtime tables are meant to lookup values that are fixed during runtime. That means, they behave in a read/write-once fashion, which is not the best possible scenario to support dynamic arrays.
• Runtime tables have a maximum preset size that is defined at the configuration level with AddRuntimeTableCfg. The best 1:1 correspondence with dynamic arrays is the capacity.
• The runtime API treats adding and querying values equally: through the lookup constraint. That means that trying to look up a value that is not intended to be in the table (for an uninitialized index) will give a satisfying constraint.
• We can define dynamic arrays with a varying length, by adding values sequentially starting from index 0, without exceeding the table length.
• First-time instantiations are cheaper as they leverage the runtime table interface quite directly.
• Modifications of the arrays are more expensive though.

Comparison

API	Naive	Runtime table
class	contains array, length, capacity	needs to keep track of runtime table id
get()	masks position i to constrain x_i	perform a lookup to table id index i and value x_i
set()	masks position i to assign new value	once a value is added to the table at a given index, it cannot change. Possibilities are: new table is created cloning id into id' except for index i which is set to the new value, a map of indices is kept track to update values
growCapacityTo_By()	returns a new instance with higher capacity but same underlying array	creating a new table with same values but more indices configured (probably in a power-of-two cadence)
increaseLength()	meant for internal use mostly, only modifies the length with some checks	no modification needed?
decreaseLength()	meant for internal use mostly, only modifies the length with some checks	no modification needed?
push()	increases length by one and sets a value in the new index	same, but setting a value happens with a lookup constraint with the new index
pop()	decreases length by n and sets trailing values to NULL	keep track of popped positions? reserve a field element for NULL?
isEmpty()	checks if length is zero	same?
shiftLeft()	length is decreased and values are moved using an offset and getters	mapping of old indices?
shiftRight()	length is increased with NULL values on the left	keep a mapping of old indices?
copy()	new instance, same array, length and capacity (currently performs no copy constraints between them)	same, but should it have a different table id in case both instances modified the arrays in a different way?
slice()	creates a new instance with the array contents from start to end, shifting left and popping	keep track of outside-bounds indices?
concat()	creates a new instance with higher capacity containing the values of both	create new table with offset indices?
insert()	increases length by 1, sets index i to the new value and then values on the right are constrained to be moved

Tradeoffs

• Some masking operations could be substituted with lookups to runtime tables.
• Reads of indices/values that had not been modified can be efficiently constrained with lookups.
• Modifications require either new tables with as many lookups as entries, or a hybrid approach with the naive solution.

Brainstorming

• The first idea that comes to mind when leveraging runtime tables to the design is to use one table per array.
  • But because of the read/write-once, would it make sense to keep track of a timeline, increasing the index of each table with the number of writes?
  • Reads would not increase the counter. Actually, the first lookup to the same index is the "valid" one. Thus, reading a different value for the same counter should give a failing constraint.
  • In that case, there wouldn't be just one table per array, but maybe one table per array index. And then the content of each index is added to the table at each step.
  • Is this reasonable? How many tables can we store in a SNARK without affecting performance?
  • Also, how many updates would be supported? It should not exceed the capacity.
  • And, how to predict the counter for the table configuration? Would it just be sequential or it depends on other steps of the computation?

[querolita]

Update:

• We are moving away from using runtime tables for dynamic arrays in favor of RAM lookups when available codespace-wise.
• Dynamic arrays in o1js #1848 in review state now

[querolita]

Update:

• Addressed issues and comments from Dynamic arrays in o1js #1848. Ready for release when approved.