feat: lazy vectors

[ivokub]

Currently we have defined vectors as []Element. However, for large vectors this introduces significant memory overhead of needing to store millions of elements in memory. In many use cases we could instead avoid reading everything into memory and compute the result in a streaming manner. For example, we could apply this to MSM where we could compute the partial MSMs and then aggregate the results.

[ivokub]

It would particularly help in https://github.com/Consensys/gnark-crypto/blob/master/ecc/bn254/mpcsetup/mpcsetup.go#L275 as we only read everything to compute a random linear combination. And in Groth16 Phase1 we provide 4 input slices. But I guess there may be other places.

[gbotrel]

Is the MSM the only use case you have in mind ? Seems to be more of a "caller's problem" ; i.e. the caller knows he needs to be memory efficient and can do the MSM in chunks and recompose.

what would an API for the MSM looks like with a "lazy" vector? also the MSM is in 2 steps, we first pre-process the scalar for the bucket business, then do the point additions in the right buckets. "shortening" the msm will impact bigO complexity

[ivokub]

I dunno yet how it would look, my first idea was a la:

type LazyVector struct {
    *os.File
    pointerLoc int
}

and then have methods Len(), Get(i), Append() (dunno?) and MultiScalarMultiplication(scalars Vectorer)

And we could wrap currently []Element or []G1Affine to make it implement the Vectorer interface so that could change interchangably.

The issue came up with Groth16 MPC setup - there for checking the correctness of the contribution we only need a random linear combination of the contribution, not the full contribution itself. And maybe we could also apply it elsewhere in gnark for proving?

---

Or, even cooler, maybe we would want to implement the range iterators introduced in Go recently? I guess it would be more idiomatic and would allow to try out as a new feature. See https://go.dev/blog/range-functions