Generate Brillig code to handle Vectors

[kevaundray]

Problem

Going to leave this unspecified as our Vector syntax is still influx.

Vectors are like arrays except for the fact that you can push to them and their sizes are not known in advanced

Happy Case

.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[kevaundray]

Prepared a list of smaller milestones after speaking with Jake:

Deprecate slice to Field sugaring (should give users a warning) (It should note that syntax is not being removed but replaced with true slices instead of desugaring to an array with known size)

Add support for slices such that in Brillig we can call an oracle and have it return a slice with length not known and enumerate over that slice

Add builtin methods to push onto slice, returning a new slice

Remove syntax sugaring in next release, see deprecation warning

[ludamad]

So an obvious thing would be to augment with yet another data type that represents a length-encoded vector, but I guess, would that cause any issues for a prover? They'd need to prove that the right length is being written otherwise memory could just be replaced with whatever the foreign function wants by giving extra data. I wonder if it makes sense to unroll this in brillig with a brillig standard library function, rather than support arbitrary length objects into/out-of brillig. Open to thoughts too

[vezenovm]

They'd need to prove that the right length is being written otherwise memory could just be replaced with whatever the foreign function wants by giving extra data

This is the most interesting aspect of this as any prover will have to prove that the right length is being written when dealing with vectors in a constrained environment. When using vectors in a constrained environment we need to perform operations such as a permutation sort (or use our blackbox RAM/ROM opcodes). A Brillig execution does always have a set amount of output witnesses, and these are determined by the evaluator. If we had Brillig return a vector the ACIR would have to correctly handle vectors as it normally does. If the Brillig evaluation leads to a set amount of witnesses returned (single value or array) this is fine as any usage of vectors inside of Brillig is unconstrained and in the Brillig VM we check that the size of the values provided from a foreign func matches the size specified in the ForeignCall opcode.

In a SNARK VM context that is executing Brillig, it does seem that the VM would have to constrain that data provided matches the values returned from a foreign call in size, but this would be the case for any foreign call no?

rather than support arbitrary length objects into/out-of brillig

Just clarifying here, do you mean dynamic arbitrary length objects at runtime vs. arbitrary length at compile time? As we already support arbitrary length objects into/out-of brillig by enabling array inputs.

[vezenovm]

Deprecate slice to Field sugaring

Do you mean slice to array? @kevaundray

[ludamad]

@vezenovm No because currently foreign arrays have a fixed size and program-determined location. If foreign arrays instead had a program-determined location and a variable size, how do we know they can't just overflow memory? Currently, don't think we can. Actually, its an impossible allocation without the size up front. For this to make sense we need

1. Dynamic alloc in brillig through a free pointer that moves with stack frames
2. It could make sense to decode slice operations as individually fixed-length operations. The other option is to have them fully allocated in brillig first. We would want to make sure the passed size meets what the program requested in either case, as otherwise malicious sequencers could clobber memory

[kevaundray]

Closing this as completed. We can open up more granular issues if something has not been addressed