This document aims to explore if using _batch affine additions_ is faster than adding in projective form for VKT MSM.

A while ago Kev mentioned this idea, and we left that convo in "We should do the counting and see", so I'm doing this here. :)

## What is _batch affine point additions_?

This is a trick [used by gnark](https://github.com/ConsenSys/gnark-crypto/pull/261) used in some cases when aggregating points in Pippenger buckets. In our case, we don't use Pippenger to do the MSM but use a precomputed list of points, but the idea can still apply (more on this later).

The idea is simple: you have N pair of affine points that you need to aggregate. That's a number of finite field multiplications and inverses. Given that you know the N pairs of affine points upfront, you can use the Montgomery trick for the inverses.

The important question is: is that faster than summing in projective form?

The answer is _it depends_. This document explores if that's the case for Bandersnatch.

## Why is this relevant for VKT MSM?

We calculate Perdersen commitments for VKTs by leveraging the fact that these MSMs are on a fixed basis, so we have some precomputed tables of affine points.

Evaluating the MSM reduces to making a bunch of additions.

Today we define a `result` projective point value and start making the additions (i.e: "mixed" additions). More details about this later.

## BLS12-381

Let's first look at the answer to the question for this curve since it's where gnark is operating and can help make sense of why the trick is useful on some curves but not others.

Doing a [point addition in affine](https://hyperelliptic.org/EFD/g1p/auto-shortw.html) is: ~`3M + 1I` (`M`=field-mul/squaring, `I`=field-inv, ).

Thus, if you have to do `n` additions:
- The cost of doing the N affine additions: `3nM + nI` operations.
- The cost using the Montgomery trick to batch inverses: `3nM + 3nM+I = 6nm + I`, depending on `n` and the cost of `I`, after some threshold `n`, the cost is ~`6nm`.
- Explanation: the Montgomery trick changes `nI` to ~`3nM+I` (i.e: a single inverse, plus some multiplications to _clear out_ terms).

If we add enough `n` pairs, the cost per affine point, addition is ~`6M` instead of `3M + I`.

Compare this to summing Jacobians, where the [cost of adding](https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html) is: ~`16M`.

Thus, for BLS12-381 there's a nice win if you have a use case that aligns with this trick.

## Bandersnatch

We have a Twisted Edwards curve, [which for affine additions means](https://hyperelliptic.org/EFD/g1p/auto-twisted.html): `8M + 2I`.

Doing analogous reasoning for `n` pairs:
- The cost of doing the N affine additions: `8nM + 2nI` operations.
- The cost using the Montgomery trick to batch inverses: `8nM + 6nM+I = 14nM + I`.

If we add enough `n` pairs, the cost per affine point addition is ~`14M` instead of `8M + I`.

Compare this to the sum in projective, where the [cost of adding](https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html): ~`11M`. Doing mixed additions (i.e: projective + affine) takes ~`10M`.

Since `14M > 11M > 10M`, it looks like, this batch affine addition trick isn't worth it for Twisted Edwards curves.